頂点被覆とは？わかりやすく解説

グラフ理論において、グラフGの頂点からなるある集合VがGの頂点被覆（ちょうてんひふく、英: vertex cover）であるとは、Gのどの辺をとってもその端点のどちらかがVに含まれるという意味である。最小頂点被覆を求める問題は計算機科学における古典的な最適化問題であり、近似アルゴリズムのある典型的なNP困難な問題でもある。その決定問題版である頂点被覆問題は計算複雑性理論における古典的なNP完全問題である。さらに頂点被覆問題には固定パラメータ容易性 (fixed-parameter tractability) があり、パラメータ化計算量理論の中心問題の1つである。

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

定義

グラフ G の頂点被覆とは頂点の集合 C であり、G の各辺は C 内の少なくとも1つの頂点と接合する。このとき集合 C は G の辺を「被覆 (cover)」すると言う。次の図は2つのグラフの頂点被覆の例を表したものである（集合 C は赤で示されている）。

最小頂点被覆 (minimum vertex cover) は、最も小さい大きさの頂点被覆である。頂点被覆数 (vertex cover number) $\tau$

例

全頂点の集合は、頂点被覆である。
頂点の集合が頂点被覆であることと、その補集合が独立集合であることは同値である。
極大マッチングの端点群は、頂点被覆を形成する。
完全2部グラフ $K_{m,n}$
このように構築した集合 C は頂点被覆である。辺 e が C によって被覆されていないとする。すると、M ∪ {e} がマッチングであり、かつ e ∉ M ということになり、M が極大マッチングであるという前提と矛盾する。さらに e = {u,v} ∈ M とすると、任意の頂点被覆（最小頂点被覆も含む）は u か v（または両方）を含まなければならず、さもなくば e が被覆されない。したがって最小頂点被覆は、M の各辺の両端の少なくとも一方を含む。まとめると、集合 C は最小頂点被覆に対して高々2倍の大きさに収まる。
この単純なアルゴリズムは、Fanica Gavril と Mihalis Yannakakis が発見した^[6]。
より複雑な技法を使うと、近似係数が若干よい近似アルゴリズムがあることが示される。例えば、近似係数 $2-\Theta \left(1/{\sqrt {\log |V|}}\right)$ の近似アルゴリズムが知られている^[7]。

近似不可能性

上述したものより良い固定係数近似アルゴリズムは知られていない。最小頂点被覆問題はAPX（英語版）完全であり、P=NPでなければ任意の係数で近似することはできない。Dinur と Safra はPCP定理の技法を使い、P=NP でなければ十分に大きな次数のグラフにおける最小頂点被覆は係数 1.3606 以内で近似できないことを証明した^[8]。さらには、unique games conjecture が真なら、最小頂点被覆は2よりよい近似係数で近似できない^[9]。
最小な頂点被覆を求めることは最大の独立集合を求めることと等価だが、近似という面からは両者は等価ではない。P=NPでなければ、独立集合問題には固定係数の近似アルゴリズムが存在しない。

ハイパーグラフの頂点被覆

頂点被覆はハイパーグラフにも自然に一般化でき、単に「ハイパーグラフの頂点被覆」とも呼ばれるが、ヒッティングセット (hitting set) という呼び方が一般化している。また、組合せ論的には横断 (transversal) とも呼ぶ。さらに言えば、ヒッティングセットと集合被覆は等価である。
形式的には、ハイパーグラフ H=(V,E) は頂点集合 V とハイパーエッジ集合 E から成る。集合 S ⊆ V がヒッティングセットとなるのは、全てのハイパーエッジ e ∈ E について S ∩ e ≠ ∅ が成り立つ場合である。計算問題としての「最小ヒッティングセット」と「ヒッティングセット問題」はグラフの場合と同様に定義される。
なお、ハイパーエッジの最大サイズが2のハイパーグラフは普通のグラフと同じである。ハイパーエッジの大きさを d までに制限すると、最小d-ヒッティングセットを求める問題にはd-近似アルゴリズムがある。

固定パラメータ容易性

ヒッティングセット問題においては、パラメータ化は異なる意味を持つ^[5]。ヒッティングセット問題はパラメータ $OPT$ について $W[2]$ -完全であり、 $f(OPT)n^{O(1)}$ という時間内で動作するアルゴリズムは存在しないと思われる。ここで $OPT$ は最小ヒッティングセットの濃度である。ヒッティングセット問題はパラメータ $OPT+d$ について固定パラメータ容易性を持つ。ここで $d$ はそのハイパーグラフの最大ハイパーエッジの大きさ $|e|$ である。より正確には、ヒッティングセット問題には $d^{OPT}n^{O(1)}$ という時間内で動作するアルゴリズムが存在する。

ヒッティングセットと集合被覆

ヒッティングセット問題は集合被覆問題と等価である。集合被覆問題の具体例は、左側に集合を頂点として置き、右側に全ての元を頂点として置き、元と集合の包含関係を辺で表した2部グラフで表すことができる。すると問題は、右側の頂点を全て被覆する左側の頂点の最小濃度の部分集合を求めることとなる。ヒッティングセット問題では、左側の頂点を全て被覆する右側の頂点の最小濃度の部分集合を求めることである。したがって、頂点の左右を入れ替えると全く同じ問題であることがわかる。

脚注

[脚注の使い方]
1. ^ Gallai, Tibor "Über extreme Punkt- und Kantenmengen." Ann. Univ. Sci. Budapest, Eotvos Sect. Math. 2, 133-138, 1959.
2. ^ Vazirani, Vijay V. (2001). Approximation Algorithms. Springer-Verlag. pp. pp.122-123. ISBN 3-540-65367-8
3. ^ Garey, M. R.; Johnson, D. S.; Stockmeyer, L. (1974), “Some simplified NP-complete problems”, Proceedings of the sixth annual ACM symposium on Theory of computing, pp. 47–63
4. ^ Garey, M. R.; D. S. Johnson (1977). “The rectilinear Steiner tree problem is NP-complete”. SIAM Journal on Applied Mathematics 32 (4): 826–834. doi:10.1137/0132071.
5. ^ ^a ^b Flum, Jörg; Grohe, Martin (2006). Parameterized Complexity Theory. Springer. ISBN 978-3-540-29952-3
6. ^ Papadimitriou, Christos H.; Steiglitz, Kenneth (1998), Combinatorial Optimization: Algorithms and Complexity, Dover , p. 432, mentions both Gavril and Yannakakis. Garey, Michael R.; Johnson, David S. (1979 [2003] エラー: 日付が正しく記入されていません。), Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman , p. 134, cites Gavril.
7. ^ George Karakostas. A better approximation ratio for the Vertex Cover problem. ECCC Report, TR04-084, 2004.
8. ^ I. Dinur and S. Safra. On the Hardness of Approximating Minimum Vertex-Cover. Annals of Mathematics, 162(1):439-485, 2005. (Preliminary version in STOC 2002, titled "On the Importance of Being Biased").
9. ^ Khot, S.; Regev, O. (2008), “Vertex cover might be hard to approximate to within 2-ε”, J. Comput. Syst. Sci. 74 (3): 335–349, doi:10.1016/j.jcss.2007.06.019 .
参考文献
- Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001). Introduction to Algorithms. Cambridge, Mass.: MIT Press and McGraw-Hill. pp. 1024–1027. ISBN 0-262-03293-7
- Michael R. Garey and David S. Johnson (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman. ISBN 0-7167-1045-5 A1.1: GT1, pg.190.
- Weisstein, Eric W. "Vertex Cover" From MathWorld.

[1] Gallai, Tibor "Über extreme Punkt- und Kantenmengen." Ann. Univ. Sci. Budapest, Eotvos Sect. Math. 2, 133-138, 1959.

[2] Vazirani, Vijay V. (2001). Approximation Algorithms. Springer-Verlag. pp. pp.122-123. ISBN 3-540-65367-8

[3] Garey, M. R.; Johnson, D. S.; Stockmeyer, L. (1974), “Some simplified NP-complete problems”, Proceedings of the sixth annual ACM symposium on Theory of computing, pp. 47–63

[4] Garey, M. R.; D. S. Johnson (1977). “The rectilinear Steiner tree problem is NP-complete”. SIAM Journal on Applied Mathematics 32 (4): 826–834. doi:10.1137/0132071.

[FlumGrohe2006-5] Flum, Jörg; Grohe, Martin (2006). Parameterized Complexity Theory. Springer. ISBN 978-3-540-29952-3

[6] Papadimitriou, Christos H.; Steiglitz, Kenneth (1998), Combinatorial Optimization: Algorithms and Complexity, Dover , p. 432, mentions both Gavril and Yannakakis. Garey, Michael R.; Johnson, David S. (1979 [2003] エラー: 日付が正しく記入されていません。), Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman , p. 134, cites Gavril.

[7] George Karakostas. A better approximation ratio for the Vertex Cover problem. ECCC Report, TR04-084, 2004.

[8] I. Dinur and S. Safra. On the Hardness of Approximating Minimum Vertex-Cover. Annals of Mathematics, 162(1):439-485, 2005. (Preliminary version in STOC 2002, titled "On the Importance of Being Biased").

[9] Khot, S.; Regev, O. (2008), “Vertex cover might be hard to approximate to within 2-ε”, J. Comput. Syst. Sci. 74 (3): 335–349, doi:10.1016/j.jcss.2007.06.019 .

[6]

[7]

[8]

[9]

[5]

頂点被覆とは？ わかりやすく解説

頂点被覆

定義

例

近似不可能性

ハイパーグラフの頂点被覆

固定パラメータ容易性

ヒッティングセットと集合被覆

脚注

参考文献

急上昇のことば

「頂点被覆」の関連用語

頂点被覆とは？わかりやすく解説