クリークカバー
最小クリーク被覆を色分けしたグラフ

グラフ理論において、クリーク被覆（クリーク被覆）またはクリークへの分割とは、与えられた無向グラフのグラフ全体を覆うクリークの集合のことである。一般的に、これはすべての頂点が被覆される必要があることを意味し、すべての辺が被覆される必要がある場合はクリーク辺被覆と呼ばれる。最小クリーク被覆とは、クリークの数を可能な限り少なくするクリーク被覆である。クリーク被覆が存在する最小のkは、与えられたグラフの クリーク被覆数と呼ばれる。

着色との関係

グラフGのクリーク被覆は、 Gの補グラフ（同じ頂点集合上のグラフで、 Gの隣接しない頂点間に辺を持つもの）のグラフ彩色とみなすことができます。クリーク被覆と同様に、グラフ彩色は頂点集合の分割ですが、クリークではなく、隣接関係のない部分集合（独立集合）への分割です。頂点の部分集合がGのクリークとなるのは、それがGの補集合の独立集合である場合に限ります。したがって、 Gの頂点の分割がGのクリーク被覆となるのは、それがGの補集合の彩色である場合に限ります。

計算の複雑さ

計算複雑性理論におけるクリーク被覆問題（クリークこうか、クリークこうか、クリーク被覆問題）は、最小のクリーク被覆を求めるアルゴリズム問題、あるいは（言い換えれば決定問題）クリーク数が所定の閾値以下となるようなクリーク被覆を求めるアルゴリズム問題である。最小クリーク被覆を求めることはNP困難であり、その決定版はNP完全である。これは、リチャード・カープが1972年に発表した論文「組合せ問題における還元可能性」でNP完全であることが示された21の問題のうちの1つである。 [ 1 ]

クリーク被覆とグラフ彩色の同値性は、グラフ彩色のNP完全性という既知の事実からクリーク被覆問題のNP完全性を証明するために使用できる縮約である。 [ 2 ]

グラフの特別なクラス

パーフェクトグラフとは、任意の誘導部分グラフに対して、彩色数（彩色における最小色数）が最大クリークのサイズに等しいグラフとして定義されます。弱パーフェクトグラフ定理によれば、パーフェクトグラフの補グラフもまたパーフェクトです。したがって、パーフェクトグラフとは、任意の誘導部分グラフ に対して、クリーク被覆数が最大独立集合のサイズに等しいグラフでもあります。パーフェクトグラフのクリーク被覆数は多項式時間で計算可能です。

最小クリーク被覆を多項式時間で求めることができるグラフの別のクラスは、三角形のないグラフです。これらのグラフでは、すべてのクリーク被覆は、マッチング（隣接する頂点の互いに素なペアの集合）と、残りのマッチングされない頂点の単独集合で構成されます。クリークの数は、頂点数からマッチングペアの数を引いた数に等しくなります。したがって、三角形のないグラフでは、最小クリーク被覆は最大マッチングを求めるアルゴリズムを用いて求めることができます。

クリークへの最適な分割は、クリーク幅が制限されたグラフに対しても多項式時間で求めることができる。[ 3 ]これらには、コグラフや距離遺伝グラフなどがあり、これらも完全グラフの一種である。

クリーク被覆問題は、立方平面グラフ[ 4 ]や単位円グラフ[ 5 ]など、他の特殊なグラフクラスではNP完全のままである。

近似

グラフ彩色において知られている近似結果の困難性は、クリーク被覆にも当てはまる。したがって、 P = NPでない限り、 n頂点グラフにおいてn 1 − εよりも良好な近似比を達成する任意のε > 0に対する多項式時間近似アルゴリズムは存在しない。[ 6 ]

各頂点が最大3つの隣接頂点を持つグラフでは、クリーク被覆はNP困難のままであり、ρ > 1 の定数が存在するため、近似比ρ以上で近似することはNP困難である。しかしながら、多項式時間で近似比 5/4 の近似値を求めることは可能である。つまり、この近似アルゴリズムは、クリーク数が最適値の 5/4 倍以下となるクリーク被覆を求める。[ 4 ]

ベイカーの手法は、平面グラフ上の問題に対して多項式時間近似スキームを提供するために使用できます。 [ 7 ]

関連するクリーク辺被覆問題は、グラフの頂点ではなく辺をクリークによって誘導される部分グラフに分割する問題である。これもNP完全である。[ 8 ]

参考文献

  1. ^ Karp, Richard (1972), "Reducibility Among Combinatorial Problems" (PDF) , in Miller, RE; Thatcher, JW (eds.), Proceedings of a Symposium on the Complexity of Computer Computations , Plenum Press, pp.  85– 103, archived from the original (PDF) on 2011-06-29 , retrieved 2008-08-29
  2. ^ガリー、マイケル・R. ;ジョンソン、デビッド・S. (1979)、「コンピュータとイントラクタビリティ：NP完全性理論へのガイド」、WHフリーマン、ISBN 0-7167-1045-5A1.2: GT19、194ページ。
  3. ^ Espelage, Wolfgang; Gurski, Frank; Wanke, Egon (2001)、「クリーク幅制限付きグラフ上のNP困難グラフ問題を多項式時間で解く方法」、International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2001)、Lecture Notes in Computer Science、vol. 2204、Springer、pp.  117– 128、doi : 10.1007/3-540-45477-2_12、ISBN 978-3-540-42707-0。
  4. ^ a b Cerioli, MR; Faria, L.; Ferreira, TO; Martinhon, CAJ; Protti, F.; Reed, B. (2008年6月)「立方グラフのクリークへの分割：平面グラフの場合、複雑性および近似」、離散応用数学、156 (12): 2270– 2278、doi : 10.1016/j.dam.2007.10.015。
  5. ^エイドリアン・ドゥミトレスク; Pach、János (2009)、「ユニット ディスク グラフの最小クリーク分割」、arXiv : 0909.1552 [ cs.CG ]。
  6. ^ Zuckerman, D. (2007)、「線形次数抽出器とMax CliqueおよびChromatic Numberの近似不可能性」(PDF)、Theory of Computing、3 : 103– 128、doi : 10.4086/toc.2007.v003a006。
  7. ^ブランシェット、マシュー; キム、イーサン; ヴェッタ、エイドリアン (2012年1月)、「スパースネットワーク上のクリーク被覆」、2012年 第14回アルゴリズム工学実験ワークショップ (ALENEX) の議事録、産業応用数学協会、pp.  93– 102、doi : 10.1137/1.9781611972924.10、ISBN 978-1-61197-212-2
  8. ^ Garey & Johnson (1979)、問題 GT59。
「 https://en.wikipedia.org/w/index.php?title=Clique_cover&oldid=1321127633」より取得