頂点被覆

頂点被覆とその最小化問題について

概要

グラフGにおける頂点被覆（vertex cover）とは、グラフの全ての辺がその端にある少なくとも一つの頂点と接続されている辺の集まりを指します。この概念はグラフ理論において重要であり、特に「最小頂点被覆問題」は、与えられたグラフに対して最小の頂点被覆の大きさを求める、計算機科学の分野において古典的かつNP完全な最適化問題として知られています。

最小頂点被覆は整数計画問題に定式化され、双対問題は最大マッチング問題と同じです。このように、頂点被覆と最大マッチングは深い結びつきがあるため、解析が多く行われています。

定義

頂点被覆Cは、グラフGの各辺がC内の少なくとも一つの頂点に接しているような頂点の集合です。このとき、CはGの辺を「被覆」していると言い、Cの最小の大きさは最小頂点被覆と呼ばれます。最小頂点被覆の大きさは「頂点被覆数」として表記され、通常τと記号化されます。

計算問題

最小頂点被覆問題は以下のように定式化されます。

• - INSTANCE: 任意のグラフG
• - OUTPUT: Gの最小頂点被覆Cの大きさk

また、決定問題としての頂点被覆問題も存在します。

• - INSTANCE: グラフGと正の整数k
• - QUESTION: Gの頂点被覆Cにおいて、その大きさがk以下であるものが存在するか？

頂点被覆問題はNP完全問題であり、計算複雑性理論においても重要な位置を占めています。特に、これにより他の問題がNP困難であることが証明されます。

属性

グラフの頂点数は、頂点被覆数と最大独立集合の大きさの和に等しいことが知られています。また、特定のグラフ、たとえば完全二部グラフK_{m,n}では、その頂点被覆数は最小の値mまたはnになります。

アルゴリズム

最小頂点被覆に関する近似アルゴリズムとして、係数2のものがあります。このアルゴリズムでは、エッジを選びその両端の頂点を被覆に加え、次にそれらの頂点をグラフから削除するという操作を繰り返します。さらに、極大マッチングを求め、その端点を頂点被覆として利用する手法もあります。

近似評価としては、従来のアルゴリズムよりも近似係数が若干良いものも存在します。これにより、より効率的に頂点被覆を求めることができるよう工夫されています。

ハイパーグラフ

頂点被覆はハイパーグラフにも拡張可能で、その場合は「ヒッティングセット（hitting set）」として知られています。形式的には、ハイパーグラフに対してヒッティングセットが成立するには、全てのハイパーエッジが少なくとも一つの要素を含む必要があります。これにより、ハイパーグラフにおいても最小ヒッティングセット問題が定義されます。

結論

頂点被覆問題は計算複雑性理論における中心的な問題であり、その解決方法は多くの応用を持っています。従って、最小頂点被覆を求めることは、計算機科学や組合せ最適化の領域において非常に重要な課題であると言えるでしょう。

もう一度検索