(1,1)-تحرير الكластر قابل للحل في وقت متعدد الحدود

الرسوم البيانية $H$ تعتبر رسومًا كليكيًا إذا كانت $H$ اتحادًا غير متقاطع للرؤوس من الكليكات. قدم أبو خزام (2017) مشكلة $(a,d)$-{تحرير التجمعات}، حيث لعددين طبيعيين ثابتين $a,d$، يُعطى رسم بياني $G$ وأوزان الرؤوس $a^:\ V(G)\rightarrow {0,1,\dots, a}$ و$d^:\ V(G)\rightarrow {0,1,\dots, d}$، ويتعين علينا تحديد ما إذا كان يمكن تحويل $G$ إلى رسم تجمعي عن طريق حذف ما لا يزيد على $d^(v)$ من الحواف المتصلة بكل رأس $v\in V(G)$ وإضافة ما لا يزيد على $a^(v)$ من الحواف المتصلة بكل رأس $v\in V(G)$. نتائج كوموسيفيتش وأولمان (2012) وأبو خزام (2017) قدّمت تصنيفًا للتعقيد (في P أو NP-كاملة) لمشكلة $(a,d)$-{تحرير التجمعات} لكل زوجي العددين $a,d$ باستثناء حالة $a=d=1$. تخمين أبو خزام (2017) أن مشكلة $(1,1)$-{تحرير التجمعات} تنتمي إلى P. نحن نحل هذا التخمين بشكل إيجابي من خلال: (i) تقديم سلسلة من خمس عمليات تقليل متعددة الحدود إلى رسوم بيانية خالية من الدورات الطولية 3 و4 ($C_3$-free و$C_4$-free) ذات الدرجة القصوى لا تتجاوز 3، و(ii) تصميم خوارزمية متعددة الحدود لحل مشكلة $(1,1)$-{تحرير التجمعات} في رسوم بيانية خالية من الدورات الطولية 3 و4 ($C_3$-free و$C_4$-free) ذات الدرجة القصوى لا تتجاوز 3.