最小クリーク被覆問題

出典: フリー百科事典『ウィキペディア(Wikipedia)』
移動: 案内検索

計算量理論において、最小のクリーク被覆(クリークひふく、: clique cover)を求めることは、グラフ理論NP完全問題である。クリーク被覆問題はリチャード・カープによるオリジナルの21問題の一つで、そのNP完全性は1972年の論文 "Reducibility Among Combinatorial Problems"(「組合せ論的問題間の還元可能性」)に示されている。

クリーク被覆問題クリーク分割問題と呼ぶこともある)とは、与えられたグラフの頂点集合を k-個のクリークへ分割できるかどうかを決定する問題である。頂点集合の k-個の集合への分割が与えられたとき、その各集合がクリークを成すかどうかは多項式時間で判定することができるから、クリーク被覆問題はNPに属する。そのNP完全性はグラフの k-彩色可能性からの帰着である。これを見るには、まずグラフ Gk-彩色可能性をその補グラフ G′ に関する事実に翻訳すればよい。このとき Gk-個のクリークへの分割は G′ の k-個の独立集合への分割を求めることに対応する(各集合にそれぞれ別の一つの色を塗ることで k-彩色ができたことになる)。

この問題と関連して、クリーク辺被覆問題というのは、与えられたグラフの辺をすべて含むようなクリークの集合を考えるもので、これもまたNP完全問題である。

参考文献[編集]