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