頂点被覆

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

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

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

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

Summarize Timeline Fact Check

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

INSTANCE: グラフ G

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

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

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

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

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

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

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

この整数計画問題（Integer Linear Pogramming; ILP）は、被覆問題と呼ばれるより大きなILPクラスに属する。このILPの整数性ギャップは 2 であり、その緩和から最小頂点被覆問題に対して係数 2 の近似アルゴリズムが得られる。さらに言えばこのILPに対する線形計画緩和は half-integral であり、全ての ${\displaystyle v\in V}$ について ${\displaystyle 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 の頂点被覆は ${\displaystyle 2^{O({\sqrt {k}})}n^{O(1)}}$ という時間で求めることができ、準指数固定パラメータ容易性がある。exponential time hypothesis によれば、平面グラフの頂点被覆問題について ${\displaystyle 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]。

より複雑な技法を使うと、近似係数が若干よい近似アルゴリズムがあることが示される。例えば、近似係数 ${\displaystyle 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でなければ、独立集合問題には固定係数の近似アルゴリズムが存在しない。