γ-クラスタリング問題：古典的及びパラメータ化された複雑性

γ-クラスタリング問題を紹介します。これは、よく知られたクラスター編集/削除/補完問題の変種であり、次のように定義されます：グラフGが与えられたとき、G内のどれだけの辺を編集、削除、または追加すれば、γ-準クリークの非重複和を得ることができるか。ここでは、これらの問題の完全な複雑性分類を提供し、NP完全問題に対する修正数でパラメータ化されたFPTアルゴリズムを示します。また、最終的なクラスター数が固定された定数であるこれらの問題の変種についても研究し、古典的およびパラメータ化された複雑性に関してほぼ同じ結果を得ました。