摘要

图 $H$ 是一个团图（clique graph），如果 $H$ 是若干个互不相交的完全子图的并集。Abu-Khzam（2017）引入了 $(a,d)$-聚类编辑问题（$(a,d)$-{Cluster Editing}），其中对于固定的自然数 $a,d$，给定一个图 $G$ 和顶点权重函数 $a^:\ V(G)\rightarrow {0,1,\dots, a}$ 及 $d^:\ V(G)\rightarrow {0,1,\dots, d}$，我们需要判断是否可以通过删除每个顶点 $v\in V(G)$ 至多 $d^(v)$ 条关联边，并添加每个顶点 $v\in V(G)$ 至多 $a^(v)$ 条关联边，将图 $G$ 转化为一个聚类图（cluster graph）。Komusiewicz 和 Uhlmann（2012）以及 Abu-Khzam（2017）的研究结果提供了 $(a,d)$-聚类编辑问题复杂性的二分法（在 P 类或 NP 完全类中），但未涵盖 $a=d=1$ 的情况。Abu-Khzam（2017）猜测 $(1,1)$-聚类编辑问题属于 P 类。我们通过以下两步肯定地解决了 Abu-Khzam 的猜想：(i) 提供了一系列五种多项式时间归约方法，将问题归约为最大度不超过 3 的不含三角形和四边形的图；(ii) 设计了一种多项式时间算法，用于解决最大度不超过 3 的不含三角形和四边形的图上的 $(1,1)$-聚类编辑问题。