グラフ $H$H がクリークグラフであるとは、$H$H がクリークの頂点互いに素な和集合であることを意味します。Abu-Khzam (2017) は $(a,d)$(a,d)-クラスタ編集問題を導入しました。これは、固定された自然数 $a,d$a,d に対して、グラフ $G$G と頂点重み関数 $a^:\ V(G)\rightarrow {0,1,\dots, a}$a: V(G)→0,1,…,a 及び $d^:\ V(G)\rightarrow {0,1,\dots, d}$d: V(G)→0,1,…,d が与えられたとき、各 $v\in V(G)$v∈V(G) について最大で $d^(v)$d(v) 個の辺を削除し、最大で $a^(v)$a(v) 個の辺を追加することで、$G$G をクラスタグラフに変形できるかどうかを決定する問題です。Komusiewicz と Uhlmann (2012) および Abu-Khzam (2017) の結果により、$(a,d)$(a,d)-クラスタ編集問題の複雑さ（P クラスまたは NP 完全）は、$a=d=1$a=d=1 の場合を除いてすべてのペア $(a,d)$(a,d) に対して二分されました。Abu-Khzam (2017) は $(1,1)$(1,1)-クラスタ編集問題が P クラスであると推測していました。本研究では、Abu-Khzam の推測を肯定的に解決するために、(i) 最大次数が3以下の $C_3$C3​ 自由かつ $C_4$C4​ 自由グラフへの5つの多項式時間還元法を提供し、(ii) 最大次数が3以下の $C_3$C3​ 自由かつ $C_4$C4​ 自由グラフに対する $(1,1)$(1,1)-クラスタ編集問題を解く多項式時間アルゴリズムを開発しました。