頂点被覆のソースを表示

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

最小頂点被覆問題は、[[整数計画問題]]に定式化でき、その[[双対問題]]は[[マッチング (グラフ理論)|最大マッチング問題]]である。

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

:[[ファイル:Vertex-cover.svg]]

'''最小頂点被覆''' (minimum vertex cover) は、最も小さい大きさの頂点被覆である。'''頂点被覆数''' (vertex cover number) <math>\tau</math> は最小頂点被覆の大きさである。次の図は2つのグラフの最小頂点被覆の例を表したものである。

:[[ファイル:Minimum-vertex-cover.svg]]

=== 例 ===
* 全頂点の集合は、頂点被覆である。
* 頂点の集合が頂点被覆であることと、その補集合が[[独立集合]]であることは[[同値]]である。
* [[マッチング (グラフ理論)|極大マッチング]]の端点群は、頂点被覆を形成する。
* [[完全2部グラフ]] <math>K_{m,n}</math> の頂点被覆数は <math>\min\{m,n\}</math> である。

=== 属性 ===
* グラフの頂点数は、頂点被覆数と最大[[独立集合]]の大きさの総和に等しい<ref>Gallai, Tibor "Über extreme Punkt- und Kantenmengen." Ann. Univ. Sci. Budapest, Eotvos Sect. Math. '''2''', 133-138, 1959.</ref>。

== 計算問題 ==
'''最小頂点被覆問題'''は、与えられたグラフの最小頂点被覆を求める[[最適化問題]]である。
:INSTANCE: グラフ ''G''
:OUTPUT: ''G'' の頂点被覆 ''C'' の大きさ ''k'' について、最小のもの。
[[決定問題]]とする場合は、これを'''頂点被覆問題'''と呼び、次のように定式化される。
:INSTANCE: グラフ ''G'' と正の整数 ''k''
:QUESTION: ''G'' の頂点被覆 ''C'' で、その大きさが ''k'' 以下のものがあるか?

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

=== 整数計画問題としての定式化 ===
各頂点にはコスト <math>c(v)\geq 0</math> が対応するものとする。（重み付き）最小頂点被覆問題は、次のように[[整数計画問題]]として定式化できる<ref>{{Cite book | last=Vazirani | first=Vijay V. | authorlink= | title=Approximation Algorithms | year=2001 | publisher=Springer-Verlag | isbn=3-540-65367-8 | pages=pp.122-123}}</ref>。
* <math>\sum_{v \in V} c(v) x_v</math> を最小化する（トータルコストを最小化）
* このとき、全ての <math>\{u,v\} \in E</math> について <math>x_u + x_v \geq 1</math> であり、（グラフの全ての辺を被覆する）
* かつ全ての <math>v\in V</math> について <math>x_v \in \{0,1\}</math> である。（全ての頂点は頂点被覆に含まれるか否かのどちらかである）
この整数計画問題(ILP)は、[[被覆問題]]と呼ばれるより大きなILPクラスに属する。このILPの[[整数性ギャップ]]は ''2'' であり、その[[線形計画緩和|緩和]]から最小頂点被覆問題に対して係数 ''2'' の[[近似アルゴリズム]]が得られる。さらに言えばこのILPの線形計画緩和は ''half-integral'' であり、全ての <math>v \in V</math> について <math>x_v\in\{0,0.5,1\}</math> の最適解が存在する。

=== 厳密な評価 ===
頂点被覆問題の[[決定問題]]版は[[NP完全問題|NP完全]]であり、正確にそれを解く効率的アルゴリズムは存在しないと思われる。NP完全であることは、3-[[充足可能性問題]]からの[[還元 (計算複雑性理論)|還元]]や、[[リチャード・カープ|カープ]]が行ったように[[最大クリーク問題|クリーク問題]]からの還元で証明できる。[[立体グラフ]]であっても頂点被覆はNP完全であるし<ref>{{Citation |first1=M. R. |last1=Garey |author1-link= |author2-link= |last2=Johnson |first2=D. S. |last3=Stockmeyer |first3=L. |authorlink3= |contribution-url= http://portal.acm.org/citation.cfm?id=803884 |contribution=Some simplified NP-complete problems |title=Proceedings of the sixth annual ACM symposium on Theory of computing |pages=47–63 |year=1974}}</ref>、[[次数 (グラフ理論)|次数]]が高々3の[[平面グラフ]]でもNP完全である<ref>{{cite journal |first=M. R. |last=Garey |authorlink= |coauthors= D. S. Johnson |title=The rectilinear Steiner tree problem is NP-complete |journal=SIAM Journal on Applied Mathematics |pages=826–834 |year=1977 |volume=32 |number=4 |doi=10.1137/0132071}}</ref>。

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

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

[[平面グラフ]]では、大きさ ''k'' の頂点被覆は ''<math>2^{O(\sqrt{k})} n^{O(1)}</math>'' という時間で求めることができ、準指数固定パラメータ容易性がある。exponential time hypothesis によれば、平面グラフの頂点被覆問題について ''<math>2^{o(\sqrt{k})} n^{O(1)}</math>'' という時間未満で解けるアルゴリズムは存在しない<ref name="FlumGrohe2006">{{cite book | last=Flum | first=Jörg | authorlink= | last2=Grohe | first2=Martin | authorlink2= | title = Parameterized Complexity Theory | year = 2006 | publisher = Springer | url = http://www.springer.com/east/home/generic/search/results?SGWID=5-40109-22-141358322-0 | isbn = 978-3-540-29952-3}}</ref>。

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

:[[ファイル:Vertex-cover-from-maximal-matching.svg]]

このように構築した集合 ''C'' は頂点被覆である。辺 ''e'' が ''C'' によって被覆されていないとする。すると、''M'' ∪ {''e''} がマッチングであり、かつ ''e'' ∉ ''M'' ということになり、''M'' が極大マッチングであるという前提と矛盾する。さらに ''e'' = {''u'',''v''} ∈ ''M'' とすると、任意の頂点被覆（最小頂点被覆も含む）は ''u'' か ''v''（または両方）を含まなければならず、さもなくば ''e'' が被覆されない。したがって最小頂点被覆は、''M'' の各辺の両端の少なくとも一方を含む。まとめると、集合 ''C'' は最小頂点被覆に対して高々2倍の大きさに収まる。

この単純なアルゴリズムは、Fanica Gavril と Mihalis Yannakakis が発見した<ref>{{citation | title=Combinatorial Optimization: Algorithms and Complexity | last1=Papadimitriou | first1=Christos H. | last2=Steiglitz | first2=Kenneth | year=1998 | publisher=Dover}}, p. 432, mentions both Gavril and Yannakakis. {{citation | title=Computers and Intractability: A Guide to the Theory of NP-Completeness | last1=Garey | first1=Michael R. | last2=Johnson | first2=David S. | year=1979 [2003] | publisher=W. H. Freeman}}, p. 134, cites Gavril.</ref>。

より複雑な技法を使うと、近似係数が若干よい近似アルゴリズムがあることが示される。例えば、近似係数 <math>2 - \Theta \left( 1 / \sqrt{\log |V|} \right)</math> の近似アルゴリズムが知られている<ref>George Karakostas. [http://eccc.hpi-web.de/eccc-reports/2004/TR04-084/index.html A better approximation ratio for the Vertex Cover problem]. ECCC Report, TR04-084, 2004.</ref>。

==== 近似不可能性 ====
上述したものより良い[[固定係数近似アルゴリズム]]は知られていない。最小頂点被覆問題は{{仮リンク|APX (計算複雑性理論)|en|APX|label=APX}}完全であり、[[P≠NP予想|'''P'''='''NP''']]でなければ任意の係数で近似することはできない。Dinur と Safra は[[PCP定理]]の技法を使い、'''P'''='''NP''' でなければ十分に大きな[[次数 (グラフ理論)|次数]]のグラフにおける最小頂点被覆は係数 1.3606 以内で近似できないことを証明した<ref>I. Dinur and S. Safra. [http://www.cs.huji.ac.il/~dinuri/mypapers/vc.pdf 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").</ref>。さらには、[[:en:unique games conjecture|unique games conjecture]] が真なら、最小頂点被覆は2よりよい近似係数で近似できない<ref>{{citation|last1=Khot|first1=S.|last2=Regev|first2=O.|title=Vertex cover might be hard to approximate to within 2-ε|journal=J. Comput. Syst. Sci.|volume=74|issue=3|year=2008|pages=335–349|doi=10.1016/j.jcss.2007.06.019}}.</ref>。

最小な頂点被覆を求めることは最大の独立集合を求めることと等価だが、近似という面からは両者は等価ではない。P=NPでなければ、独立集合問題には固定係数の近似アルゴリズムが存在しない。

== ハイパーグラフの頂点被覆 ==
頂点被覆は[[ハイパーグラフ]]にも自然に一般化でき、単に「ハイパーグラフの頂点被覆」とも呼ばれるが、'''ヒッティングセット''' (hitting set) という呼び方が一般化している。また、組合せ論的には'''横断''' (transversal) とも呼ぶ。さらに言えば、ヒッティングセットと[[集合被覆問題|集合被覆]]は等価である。

形式的には、ハイパーグラフ ''H=(V,E)'' は頂点集合 ''V'' とハイパーエッジ集合 ''E'' から成る。集合 ''S &sube; V'' がヒッティングセットとなるのは、全てのハイパーエッジ ''e &isin; E'' について ''S &cap; e &ne; &empty;'' が成り立つ場合である。計算問題としての「最小ヒッティングセット」と「ヒッティングセット問題」はグラフの場合と同様に定義される。

なお、ハイパーエッジの最大サイズが2のハイパーグラフは普通のグラフと同じである。ハイパーエッジの大きさを ''d'' までに制限すると、最小''d''-ヒッティングセットを求める問題には[[:en:K-approximation of k-hitting set|d-近似]]アルゴリズムがある。

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

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

== 脚注・出典 ==
{{Reflist}}

==参考文献==
* {{Cite book | last=Cormen | first=Thomas H. | authorlink= | last2=Leiserson | first2=Charles E. | authorlink2= | last3=Rivest | first3=Ronald L.  | authorlink3=ロナルド・リベスト | last4=Stein | first4=Clifford | authorlink4= | title=Introduction to Algorithms | year=2001 | publisher=MIT Press and McGraw-Hill | location=Cambridge, Mass. | isbn=0-262-03293-7 | pages=1024–1027}}
* {{cite book|author = Michael R. Garey and David S. Johnson | year = 1979|title =Computers and Intractability: A Guide to the Theory of NP-Completeness | publisher = W.H. Freeman | isbn = 0-7167-1045-5}} A1.1: GT1, pg.190.
* Weisstein, Eric W. "[http://mathworld.wolfram.com/VertexCover.html Vertex Cover]" From [http://mathworld.wolfram.com/ MathWorld].

{{DEFAULTSORT:ちようてんひふく}}
[[Category:グラフ理論]]
[[Category:計算複雑性理論]]
[[Category:数学に関する記事]]