Loading article…
グラフ理論では、与えられた無向グラフのクリーク被覆またはクリークへの分割は、グラフ全体を覆うクリークの集合です。最小クリーク被覆は、できるだけ少ないクリークを使用するクリーク被覆です。クリーク被覆が存在する最小の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]
参考文献
- ^ Karp, Richard (1972)、「組合せ問題における縮減可能性」(PDF)、Miller, RE; Thatcher, JW (編)、Proceedings of a Symposium on the Complexity of Computer Computations 、Plenum Press、pp. 85–103、2011-06-29にオリジナル(PDF)からアーカイブ、2008-08-29取得
- ^ ガリー、マイケル・R. ;ジョンソン、デビッド・S. (1979)、コンピュータとイントラクタビリティ：NP完全性理論ガイド、WHフリーマン、ISBN 0-7167-1045-5A1.2: GT19、194ページ。
- ^ Espelage, Wolfgang; Gurski, Frank; Wanke, Egon (2001)、「クリーク幅制限グラフ上の NP 困難なグラフ問題を多項式時間で解く方法」、コンピュータ サイエンスにおけるグラフ理論的概念に関する国際ワークショップ (WG 2001)、コンピュータ サイエンスの講義ノート、vol. 2204、Springer、pp. 117–128、doi :10.1007/3-540-45477-2_12、ISBN 978-3-540-42707-0。
- ^ ab Cerioli, MR; Faria, L.; Ferreira, TO; Martinhon, CAJ; Protti, F.; Reed, B. (2008 年 6 月)、「立方グラフのクリークへの分割: 平面ケース、複雑性、近似」、Discrete Applied Mathematics、156 (12): 2270–2278、doi : 10.1016/j.dam.2007.10.015。
- ^ エイドリアン・ドゥミトレスク; Pach、János (2009)、「ユニット ディスク グラフの最小クリーク分割」、arXiv : 0909.1552 [cs.CG]。
- ^ Zuckerman, D. (2007)、「線形次数抽出器と最大クリークおよび彩色数の近似不可能性」(PDF)、Theory of Computing、3 : 103–128、doi : 10.4086/toc.2007.v003a006。
- ^ ブランシェット、マシュー、キム、イーサン、ヴェッタ、エイドリアン（2012年1月）、「スパースネットワーク上のクリークカバー」、2012年第14回アルゴリズムエンジニアリングおよび実験ワークショップ（ALENEX）の議事録、産業応用数学協会、pp. 93–102、doi：10.1137/1.9781611972924.10、ISBN 978-1-61197-212-2
- ^ ゲイリー & ジョンソン (1979)、問題 GT59。