论文标题
（1,1） - 集体编辑是多项式时间可溶剂
(1,1)-Cluster Editing is Polynomial-time Solvable
论文作者
论文摘要
图形$ h $是集团图，如果$ h $是一个顶点disjoin cliques联合。 Abu-Khzam（2017）介绍了$（a，d）$ - {cluster编辑}问题，其中固定的自然数量$ a，d $，给定图形$ g $和vertex-weights $ a^*：\ v（g） \ {0,1，\ dots，d \} $，我们要通过最多删除$ d^*（v）$ edges in v（g）$中的每个$ v \ in v（g）$中的每个$ v \ ind $ a^*（v）$ edges in（v）$ v \ in（g）$。 Results by Komusiewicz and Uhlmann (2012) and Abu-Khzam (2017) provided a dichotomy of complexity (in P or NP-complete) of $(a,d)$-{Cluster Editing} for all pairs $a,d$ apart from $a=d=1.$ Abu-Khzam (2017) conjectured that $(1,1)$-{Cluster Editing} is in P. We解决Abu-khzam在肯定中的猜想（i）通过（i）认真对$ C_3 $ -FREE和$ C_4 $ - 最高学位的最高学位的$ C_3 $ - Free图，以及（ii）设计一个多项式时间算法，用于求解$（1,1）$ - $ c的$ c_3 $ c.3 $ c $ c_3 $ c_3 $ c_3最高学位最多3。
A graph $H$ is a clique graph if $H$ is a vertex-disjoin union of cliques. Abu-Khzam (2017) introduced the $(a,d)$-{Cluster Editing} problem, where for fixed natural numbers $a,d$, given a graph $G$ and vertex-weights $a^*:\ V(G)\rightarrow \{0,1,\dots, a\}$ and $d^*{}:\ V(G)\rightarrow \{0,1,\dots, d\}$, we are to decide whether $G$ can be turned into a cluster graph by deleting at most $d^*(v)$ edges incident to every $v\in V(G)$ and adding at most $a^*(v)$ edges incident to every $v\in V(G)$. Results by Komusiewicz and Uhlmann (2012) and Abu-Khzam (2017) provided a dichotomy of complexity (in P or NP-complete) of $(a,d)$-{Cluster Editing} for all pairs $a,d$ apart from $a=d=1.$ Abu-Khzam (2017) conjectured that $(1,1)$-{Cluster Editing} is in P. We resolve Abu-Khzam's conjecture in affirmative by (i) providing a serious of five polynomial-time reductions to $C_3$-free and $C_4$-free graphs of maximum degree at most 3, and (ii) designing a polynomial-time algorithm for solving $(1,1)$-{Cluster Editing} on $C_3$-free and $C_4$-free graphs of maximum degree at most 3.
