頂点被覆

グラフ理論において、グラフ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つのグラフの最小頂点被覆の例を表したものである。

例

全頂点の集合は、頂点被覆である。
頂点の集合が頂点被覆であることと、その補集合が独立集合であることは同値である。
極大マッチングの端点群は、頂点被覆を形成する。
完全2部グラフ $K_{m,n}$ の頂点被覆数は $\min\{m,n\}$ である。

属性

グラフの頂点数は、頂点被覆数と最大独立集合の大きさの総和に等しい^[1]。

計算問題

最小頂点被覆問題は、与えられたグラフの最小頂点被覆を求める最適化問題である。

INSTANCE: グラフ G

OUTPUT: G の頂点被覆 C の大きさ k について、最小のもの。

決定問題とする場合は、これを頂点被覆問題と呼び、次のように定式化される。

INSTANCE: グラフ G と正の整数 k

QUESTION: G の頂点被覆 C で、その大きさが k 以下のものがあるか?

頂点被覆問題はNP完全問題である。カープの21のNP完全問題の1つになっており、他の問題がNP困難であることを示す手段として計算複雑性理論でよく利用される。

整数計画問題としての定式化

各頂点にはコスト $c(v)\geq 0$ が対応するものとする。（重み付き）最小頂点被覆問題は、次のように整数計画問題として定式化できる^[2]。

$\sum _{v\in V}c(v)x_{v}$ を最小化する（トータルコストを最小化）
このとき、全ての $\{u,v\}\in E$ について $x_{u}+x_{v}\geq 1$ であり、（グラフの全ての辺を被覆する）
かつ全ての $v\in V$ について $x_{v}\in \{0,1\}$ である。（全ての頂点は頂点被覆に含まれるか否かのどちらかである）

この整数計画問題(ILP)は、被覆問題と呼ばれるより大きなILPクラスに属する。このILPの整数性ギャップは 2 であり、その緩和から最小頂点被覆問題に対して係数 2 の近似アルゴリズムが得られる。さらに言えばこのILPの線形計画緩和は half-integral であり、全ての $v\in V$ について $x_{v}\in \{0,0.5,1\}$ の最適解が存在する。

厳密な評価

頂点被覆問題の決定問題版はNP完全であり、正確にそれを解く効率的アルゴリズムは存在しないと思われる。NP完全であることは、3-充足可能性問題からの還元や、カープが行ったようにクリーク問題からの還元で証明できる。立体グラフであっても頂点被覆はNP完全であるし^[3]、次数が高々3の平面グラフでもNP完全である^[4]。

2部グラフの場合、König's theorem から頂点被覆と最大マッチングの等価性が示されているので、2部頂点被覆問題は多項式時間で解ける。

固定パラメータ容易性

力まかせ探索アルゴリズムを使えば、2^O(k)n^O(1) の時間で問題を解くことができる。したがって頂点被覆は固定パラメータ容易性があり、小さい k のみに着目する場合は多項式時間で問題を解くことができる。このときのアルゴリズム的技法として bounded search tree algorithm があり、頂点の選択を繰り返し、現在の頂点を頂点被覆に含めるか、隣接する全頂点を頂点被覆に含めるかを再帰的に選択していくものである。計算複雑性理論における exponential time hypothesis という仮説によれば、この方式の実行時間は 2^o(k)n^O(1) より改善されることはない。

平面グラフでは、大きさ k の頂点被覆は $2^{O({\sqrt {k}})}n^{O(1)}$ という時間で求めることができ、準指数固定パラメータ容易性がある。exponential time hypothesis によれば、平面グラフの頂点被覆問題について $2^{o({\sqrt {k}})}n^{O(1)}$ という時間未満で解けるアルゴリズムは存在しない^[5]。

近似評価

係数が2の近似アルゴリズムがあり、辺を選んでその両端の頂点を頂点被覆に入れ、グラフからそれらを削除するということを繰り返す。あるいは、力まかせアルゴリズムで極大マッチング M を求め、M に属する全端点から頂点被覆 C を構築するという方法もある。次の図では、極大マッチング M を赤で示し、頂点被覆 C を青で示している。

このように構築した集合 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部グラフで表すことができる。すると問題は、右側の頂点を全て被覆する左側の頂点の最小濃度の部分集合を求めることとなる。ヒッティングセット問題では、左側の頂点を全て被覆する右側の頂点の最小濃度の部分集合を求めることである。したがって、頂点の左右を入れ替えると全く同じ問題であることがわかる。

脚注・出典

^ Gallai, Tibor "Über extreme Punkt- und Kantenmengen." Ann. Univ. Sci. Budapest, Eotvos Sect. Math. 2, 133-138, 1959.
^ Vazirani, Vijay V. (2001). Approximation Algorithms. Springer-Verlag. pp. pp.122-123. ISBN 3-540-65367-8
^ 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
^ 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.
^ ^a ^b Flum, Jörg; Grohe, Martin (2006). Parameterized Complexity Theory. Springer. ISBN 978-3-540-29952-3
^ 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.
^ George Karakostas. A better approximation ratio for the Vertex Cover problem. ECCC Report, TR04-084, 2004.
^ 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").
^ 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 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]