頂点カバー

グラフ理論において、グラフの頂点被覆（ノード被覆とも呼ばれる）とは、グラフのすべての辺の少なくとも1つの端点を含む頂点の集合のことである。

コンピュータサイエンスにおいて、最小頂点被覆を見つける問題は古典的な最適化問題です。これはNP困難であるため、 P≠NPの場合、多項式時間アルゴリズムでは解くことができません。さらに、近似も困難です。ユニークゲーム予想が正しい場合、2より小さい係数まで近似することはできません。一方で、いくつかの単純な2係数近似が存在します。これは、近似アルゴリズムを持つNP困難な最適化問題の典型的な例です。その決定版である頂点被覆問題は、 Karpの21のNP完全問題の1つであり、したがって計算複雑性理論における古典的なNP完全問題です。さらに、頂点被覆問題は固定パラメータ扱い可能であり、パラメータ化複雑性理論の中心的な問題です。

最小頂点被覆問題は、半整数線形計画問題として定式化でき、その双対線形計画問題は最大マッチング問題である。

頂点被覆問題はハイパーグラフに一般化されている。ハイパーグラフにおける頂点被覆を参照のこと。

意味

正式には、頂点カバー $V'$ 無向グラフの $G=(V,E)$ は、 $V$ そのため $(uv\in E)\Rightarrow (u\in V'\lor v\in V')$ つまり、それは頂点の集合である。 $V'$ すべての辺が頂点被覆内に少なくとも1つの端点を持つ $V'$ このようなセットは、 $G$ 上の図は、頂点被覆の2つの例を示しています。 $V'$ 赤色でマークされています。

最小頂点被覆とは、可能な限り最小サイズの頂点被覆のことです。頂点被覆数 $\displaystyle \tau }$ は最小頂点被覆のサイズです。 $\tau =|V'|$ 下の図は、前のグラフにおける最小頂点被覆の例を示しています。

例

すべての頂点の集合は頂点被覆である。
任意の最大マッチングの端点は頂点被覆を形成する。
完全二部グラフ $K_{m,n}$ 最小頂点被覆サイズを持つ $\tau (K_{m,n})=\min\{\,m,n\,\}$ 。

物件

頂点の集合が頂点被覆であるのは、その補集合が独立集合である場合に限る。
したがって、グラフの頂点の数は、その最小頂点被覆数と最大独立集合のサイズの合計に等しくなります。^{[ 1 ]}

計算上の問題

最小頂点被覆問題とは、与えられたグラフにおいて最小の頂点被覆を見つける最適化問題である。

インスタンス: グラフ

G

出力：最小値

k

そのため

G

頂点カバーのサイズは

k

。

問題が決定問題として定式化される場合、それは頂点被覆問題と呼ばれます。

インスタンス: グラフ

G

正の整数

k

。

質問：

G

頂点カバーのサイズは最大で

k

？

これらは、二分探索を用いた多項式時間還元において等価である。頂点被覆問題はNP完全問題であり、カープが挙げた21のNP完全問題の一つである。計算複雑性理論において、NP困難性の証明の出発点としてしばしば用いられる。

ILP製剤

すべての頂点には、以下のコストが関連付けられていると仮定します。 $c(v)\geq 0$ （重み付き）最小頂点被覆問題は、次の整数線形計画問題（ILP）として定式化できる。 ^{[ 2 ]}

このILPは、被覆問題に対するより一般的なクラスのILPに属します。このILPの整数性ギャップは $2$ 、そのため緩和（各変数が0または1のみである必要はなく、0から1の区間にあることを許容する）により、係数- $2$ 最小頂点被覆問題に対する近似アルゴリズム。さらに、そのILPの線形計画緩和は半整数であり、つまり、各エントリに対して最適解が存在する。 $x_{v}$ は 0、1/2、または 1 のいずれかです。この分数解から、変数がゼロでない頂点のサブセットを選択することで、2 近似頂点被覆を得ることができます。

正確な評価

頂点被覆問題の決定版はNP完全であり、これは任意のグラフに対してそれを正確に解く効率的なアルゴリズムが存在する可能性が低いことを意味します。NP完全性は、3充足可能性からの還元、またはKarpが行ったようにクリーク問題からの還元によって証明できます。頂点被覆問題は、 3次グラフ^{[ 3 ]}や次数が最大3の平面グラフ^[⁴^]でもNP完全のままです。

二部グラフの場合、ケーニッヒの定理で説明される頂点被覆と最大マッチングの等価性により、二部グラフの頂点被覆問題を多項式時間で解くことができます。

木グラフの場合、アルゴリズムは、木の最初の葉を見つけてその親を最小頂点被覆に追加し、次に葉と親および関連するすべてのエッジを削除し、木にエッジが残らなくなるまで繰り返し続けることにより、多項式時間で最小頂点被覆を見つけます。

固定パラメータの扱いやすさ

網羅的探索アルゴリズムは、この問題を 2 ^k n ^{O (1)}の時間で解くことができます。ここで、kは頂点被覆のサイズです。したがって、頂点被覆は固定パラメータ扱い可能であり、小さなkのみに関心がある場合は、この問題を多項式時間で解くことができます。ここで有効なアルゴリズム手法の 1 つは、有界探索木アルゴリズムと呼ばれ、そのアイデアは、いくつかの頂点を繰り返し選択し、各ステップで 2 つのケースで再帰的に分岐することです。現在の頂点またはそのすべての隣接頂点を頂点被覆に配置する場合です。パラメータに対する最良の漸近依存性を達成する頂点被覆を解くアルゴリズムは、時間で実行されます。 $O(1.2738^{k}+(k\cdot n))$ ^{[ 5 ]}この時間制限のklam 値(妥当な時間で解ける最大のパラメータ値の推定値) は約 190 です。つまり、追加のアルゴリズムの改善が見つからない限り、このアルゴリズムは頂点被覆数が 190 以下のインスタンスにのみ適しています。妥当な複雑性理論の仮定、すなわち指数時間仮説の下では、実行時間は 2 ^{o ( k )}に改善することはできません。 $n$ は $O(k)$ 。

しかし、平面グラフ、より一般的には、ある固定グラフをマイナーとして除外するグラフの場合、サイズkの頂点被覆は時間で見つけることができます。 $2^{O({\sqrt {k}})}n^{O(1)}$ すなわち、この問題は準指数時間固定パラメータ扱い可能である。^{[ 6 ]}このアルゴリズムは、指数時間仮説の下では、平面グラフ上の頂点被覆問題を時間内に解くアルゴリズムは存在しないという意味で、最適である。 $2^{o({\sqrt {k}})}n^{O(1)}$ [ ⁷^]

おおよその評価

エッジの両端点を頂点カバーに繰り返し取り込んでからグラフから取り除くことで、係数2の近似値を求めることができます。言い換えれば、貪欲アルゴリズムを用いて最大マッチングMを見つけ、 Mに含まれるエッジのすべての端点からなる頂点カバーCを構築します。次の図では、最大マッチングMを赤色で、頂点カバーCを青色で示しています。

このようにして構築された集合Cは頂点被覆です。辺eがCで被覆されていないと仮定すると、M ∪ { e } はマッチングであり、e ∉ Mとなります。これは、 Mが極大であるという仮定と矛盾します。さらに、e = { u , v } ∈ Mの場合、最適な頂点被覆を含む任意の頂点被覆は、uまたはv (あるいはその両方) を含まなければなりません。そうでなければ、辺eは被覆されていません。つまり、最適な被覆は、 Mの各辺の少なくとも1 つの端点を含みます。全体として、集合Cは最適な頂点被覆の最大 2 倍の大きさになります。

このシンプルなアルゴリズムは、ファニカ・ガヴリルとミハリス・ヤナカキスによって独立に発見された。^{[ 8 ]}

より高度な手法では、わずかに近似係数の優れた近似アルゴリズムが存在することが示されています。たとえば、近似係数が ${\textstyle 2-\Theta \left(1/{\sqrt {\log |V|}}\right)}$ は既知である。^{[ 9 ]}この問題は近似係数を用いて近似することができる。 $2/(1+\delta )$ で $\delta$ - 密なグラフ。^{[ 10 ]}

近似不可能性

上記のアルゴリズムよりも優れた定数係数近似アルゴリズムは知られていない。最小頂点被覆問題はAPX完全問題であり、 P = NP でない限り、任意の精度で近似することはできない。PCP定理の手法を用いて、DinurとSafraは2005年に、 P = NPでない限り、任意の十分に大きな頂点次数に対して最小頂点被覆を1.3606の係数で近似することはできないことを証明した。^[¹¹^] 後に、この係数は改善され、 ${\sqrt {2}}-\epsilon$ いかなる場合でも $\epsilon >0$ ^{[ 12 ]} さらに、ユニークゲーム予想が正しい場合、最小頂点被覆は2より小さい定数係数で近似することはできません。^{[ 13 ]}

最小サイズの頂点被覆を見つけることは、上記のように最大サイズの独立集合を見つけることと同等ですが、2 つの問題は近似値を保持する形で同等ではありません。独立集合問題には、 P = NPでない限り定数係数近似はありません。

擬似コード

近似アルゴリズム: ^{[ 14 ]}^{[ 15 ]}

近似-頂点-カバー( G ) C = ∅ E ' = G . EE ' ≠ ∅の間、( u , v )をE 'の任意の辺とする。C = C ∪ { u , v } uまたはvに接続するすべての辺をE 'から削除する。Cを返す

注記

↑ガライ 1959。
↑ヴァジラニ 2003 、 121–122ページ
↑ゲイリー、ジョンソン＆ストックマイヤー 1974
↑ゲイリー＆ジョンソン 1977 ;ゲイリー＆ジョンソン、1979 年、190 および 195 ページ。
↑チェン、カンジ、シア 2006
↑デメインら、2005年
↑ Flum & Grohe (2006 、p. 437)
↑パパディミトリウ&スタイグリッツ 1998 年、p. 432、ガブリルとヤナカキスの両方について言及されています。ゲイリー＆ジョンソン 1979 年、p. 134、ガブリルは引用する。
↑カラコスタス 2009
↑カルピンスキー＆ゼリコフスキー 1998
↑ディヌール＆サフラ 2005
↑コート、ミンザー、サフラ 2017 ;ディヌールら。 2018年;コート、ミンザー、サフラ 2018
↑ Khot & Regev 2008
↑ Cormen, Thomas H. ; Leiserson, Charles E. ; Rivest, Ronald L. ; Stein, Clifford (2001) [1990]. "Section 35.1: The vertex-cover problem". Introduction to Algorithms (2nd ed.). MIT Press and McGraw-Hill. pp. 1024–1027 . ISBN 0-262-03293-7。
↑ Chakrabarti, Amit (2005年冬)。「近似アルゴリズム：頂点被覆」(PDF)。コンピュータサイエンス105。ダートマス大学。 2005年2月21日取得。

参考文献

Chen, Jianer; Kanj, Iyad A.; Xia, Ge (2006). "Improved Parameterized Upper Bounds for Vertex Cover". Mathematical Foundations of Computer Science 2006: 31st International Symposium, MFCS 2006, Stará Lesná, Slovakia, August 28-September 1, 2006, Proceedings (PDF) . Lecture Notes in Computer Science. Vol. 4162. Springer-Verlag. pp. 238–249 . doi : 10.1007/11821069_21 . ISBN 978-3-540-37791-7。
トーマス・H・コーメン;チャールズ・E・ライザーソン;ロナルド・L・リベスト;スタイン、クリフォード(2001)。アルゴリズムの概要。マサチューセッツ州ケンブリッジ: MIT Press および McGraw-Hill。1024 –1027ページ。ISBN 0-262-03293-7。
エリック・ディメイン;フォミン、ヒョードル V.ハジアガイ、モハマド・タギ。ティリコス、ディミトリオス M. (2005)。「有界種数グラフおよび H マイナーフリーグラフにおける準指数関数パラメータ化アルゴリズム」。ACM のジャーナル。52 (6): 866–893 .土井: 10.1145/1101821.1101823。S2CID 6238832 。2010 年 3 月 5 日に取得。
Dinur, Irit ; Khot, Subhash ; Kindler, Guy; Minzer, Dor; Safra, Muli (2018). 「2対1ゲーム予想の証明に向けて？」. Diakonikolas, Ilias; Kempe, David; Henzinger, Monika (編).第50回ACM SIGACT理論計算機科学シンポジウム（STOC 2018）議事録、米国カリフォルニア州ロサンゼルス、2018年6月25日～29日. Association for Computing Machinery. pp. 376–389 . doi : 10.1145/3188745.3188804 . ISBN 978-1-4503-5559-9ECCC TR16-198。
Dinur, Irit ; Safra, Samuel (2005). 「最小頂点被覆の近似の難しさについて」. Annals of Mathematics . 162 (1): 439–485 . CiteSeerX 10.1.1.125.334 . doi : 10.4007/annals.2005.162.439 .
Flum, Jörg; Grohe, Martin (2006). Parameterized Complexity Theory . Springer. doi : 10.1007/3-540-29953-X . ISBN 978-3-540-29952-32010年3月5日に取得。
Garey, Michael R. ; Johnson, David S. (1977). "直線シュタイナー木問題はNP完全である". SIAM Journal on Applied Mathematics . 32 (4): 826– 834. doi : 10.1137/0132071 .
ゲイリー、マイケル・R.、ジョンソン、デイビッド・S. (1979).コンピュータと難解性：NP完全性理論への手引き. WHフリーマン. ISBN 0-7167-1045-5。A1.1: GT1、190ページ。
Garey, Michael R. ; Johnson, David S. ; Stockmeyer, Larry (1974). 「いくつかの単純化されたNP完全問題」 .第6回ACM理論計算機科学シンポジウム議事録. pp. 47–63 . doi : 10.1145/800119.803884 .
ガライ、ティボール(1959)。「ユーバーエクストリームプンクトウントカンテンメンゲン」。アン。大学科学。ブダペスト、エトヴェシュ支部数学。2：133～ 138。
Karakostas, George (2009年11月). 「頂点被覆問題に対するより良い近似比」(PDF) . ACM Transactions on Algorithms . 5 (4): 41:1–41:8. CiteSeerX 10.1.1.649.7407 . doi : 10.1145/1597036.1597045 . S2CID 2525818 . ECCC TR04-084 .
Karpinski, Marek; Zelikovsky, Alexander (1998). 「被覆問題の密なケースの近似」 . DIMACSワークショップ「ネットワーク設計：接続性と設備配置」論文集. DIMACS離散数学および理論計算機科学シリーズ. 第 40巻. アメリカ数学会. pp. 169–178 .
Khot, Subhash ; Minzer, Dor; Safra, Muli (2017). 「独立集合、2対2ゲーム、グラスマングラフについて」Hatami, Hamed; McKenzie, Pierre; King, Valerie (編)『第49回ACM SIGACT理論計算機科学シンポジウム（STOC 2017）議事録』、モントリオール、ケベック州、カナダ、2017 年6月19日～23日。Association for Computing Machinery。pp. 576–589。doi : 10.1145/3055399.3055432。ISBN 978-1-4503-4528-6ECCC TR16-124。
Khot, Subhash ; Minzer, Dor; Safra, Muli (2018). 「グラスマングラフにおける擬似乱数集合はほぼ完全な拡張性を持つ」. 2018 IEEE 第 59 回コンピュータサイエンス基礎に関する年次シンポジウム (FOCS) . pp. 592–601 . doi : 10.1109/FOCS.2018.00062 . ISBN 978-1-5386-4230-6. S2CID 3688775 .
Khot, Subhash ; Regev, Oded (2008). "頂点被覆は 2 − ε以内で近似するのが難しいかもしれない" . Journal of Computer and System Sciences . 74 (3): 335– 349. doi : 10.1016/j.jcss.2007.06.019 .
パパディミトリウ、クリストス H. ;スティーグリッツ、ケネス(1998).組み合わせ最適化: アルゴリズムと複雑性. ドーバー出版.
ヴァジラニ、ビジェイ V. (2003)。近似アルゴリズム。スプリンガー・フェルラーク。ISBN 978-3-662-04565-7。

外部リンク

Weisstein, Eric W. 「頂点カバー」 . MathWorld .
Weisstein, Eric W. 「最小頂点被覆」 . MathWorld .
Weisstein, Eric W. 「頂点被覆数」 . MathWorld .
川の横断（とアルクイン数） – ナンバーファイル

[FOOTNOTEGallai1959-1] ガライ 1959。

[2] ヴァジラニ 2003 、 121–122ページ

[3] ゲイリー、ジョンソン＆ストックマイヤー 1974

[4] ゲイリー＆ジョンソン 1977 ;ゲイリー＆ジョンソン、1979 年、190 および 195 ページ。

[5] チェン、カンジ、シア 2006

[6] デメインら、2005年

[7] Flum & Grohe (2006 、p. 437)

[8] パパディミトリウ&スタイグリッツ 1998 年、p. 432、ガブリルとヤナカキスの両方について言及されています。ゲイリー＆ジョンソン 1979 年、p. 134、ガブリルは引用する。

[9] カラコスタス 2009

[10] カルピンスキー＆ゼリコフスキー 1998

[11] ディヌール＆サフラ 2005

[12] コート、ミンザー、サフラ 2017 ;ディヌールら。 2018年;コート、ミンザー、サフラ 2018

[kr08-13] Khot & Regev 2008

[14] Cormen, Thomas H. ; Leiserson, Charles E. ; Rivest, Ronald L. ; Stein, Clifford (2001) [1990]. "Section 35.1: The vertex-cover problem". Introduction to Algorithms (2nd ed.). MIT Press and McGraw-Hill. pp. 1024–1027 . ISBN 0-262-03293-7。

[15] Chakrabarti, Amit (2005年冬)。「近似アルゴリズム：頂点被覆」(PDF)。コンピュータサイエンス105。ダートマス大学。 2005年2月21日取得。

[ 1 ]

[ 2 ]

[ 3 ]

[

[ 5 ]

[ 6 ]

7

[ 8 ]

[ 9 ]

[ 10 ]

[

[ 12 ]

[ 13 ]

[ 14 ]

[ 15 ]