頂点カバー

グラフ理論では、グラフの頂点カバー（ノードカバーと呼ばれることもある）は 、グラフの すべての辺の少なくとも 1 つの端点を含む頂点の集合です。

コンピュータ サイエンスでは、最小の頂点被覆を見つける問題は古典的な最適化問題です。これはNP 困難であるため、 P ≠ NPの場合、多項式時間アルゴリズムでは解くことができません。また、近似も困難で、ユニーク ゲーム予想が正しい場合、2 未満の因数に近似することはできません。一方で、この問題にはいくつかの単純な 2 因数近似があります。これは、近似アルゴリズムを持つ NP 困難な最適化問題の典型的な例です。その決定バージョンである頂点被覆問題は、 Karp の 21 の NP 完全問題の 1 つであったため、計算複雑性理論における古典的なNP 完全問題です。さらに、頂点被覆問題は固定パラメータで扱いやすく、パラメータ化された複雑性理論における中心的な問題です。

最小頂点カバー問題は、半積分線形計画法として定式化することができ、その双対線形計画法は最大マッチング問題です。

頂点被覆問題はハイパーグラフに一般化されています。ハイパーグラフの頂点被覆を参照してください。

正式には、無向グラフの頂点被覆はとなる のサブセット、つまり、すべての辺が頂点被覆 内に少なくとも 1 つの端点を持つ頂点の集合です。このような集合はの辺を被覆すると言われています。上の図は、頂点被覆の 2 つの例を示しており、一部の頂点被覆は赤でマークされています。 ${\displaystyle V'}$${\displaystyle G=(V,E)}$${\displaystyle V}$${\displaystyle uv\in E\Rightarrow u\in V'\lor v\in V'}$${\displaystyle V'}$${\displaystyle V'}$${\displaystyle G}$${\displaystyle V'}$

最小頂点カバーとは、可能な限り最小のサイズの頂点カバーです。頂点カバー数は、最小頂点カバーのサイズ、つまり です。下の図は、前のグラフの最小頂点カバーの例を示しています。 ${\displaystyle \tau }$${\displaystyle \tau =|V'|}$

• すべての頂点の集合は頂点カバーです。
• 任意の最大マッチングの端点は頂点カバーを形成します。
• 完全二部グラフには、 サイズ の最小頂点カバーがあります。${\displaystyle K_{m,n}}$${\displaystyle \tau (K_{m,n})=\min\{\,m,n\,\}}$

• 頂点の集合は、その補集合が独立集合である場合に限り、頂点被覆となります。
• その結果、グラフの頂点の数は、その最小頂点被覆数と最大独立集合のサイズの合計に等しくなります。^[1]

最小頂点カバー問題は、与えられたグラフ内で最小の頂点カバーを見つける 最適化問題です。

インスタンス: グラフ${\displaystyle G}$

出力:頂点カバーのサイズを持つ最小の数値。${\displaystyle k}$${\displaystyle G}$${\displaystyle k}$

この問題が決定問題として表現される場合、それは頂点カバー問題と呼ばれます。

インスタンス: グラフと正の整数。${\displaystyle G}$${\displaystyle k}$

質問:最大で のサイズの頂点カバーがありますか?${\displaystyle G}$${\displaystyle k}$

頂点カバー問題はNP 完全問題です。これは、Karp の 21 個の NP 完全問題のうちの 1 つです。これは、NP 困難性の証明 の出発点として、計算複雑性理論でよく使用されます。

すべての頂点には のコストが関連していると仮定します。（重み付き）最小頂点カバー問題は、次の整数線形計画（ILP）として定式化できます。^[2]${\displaystyle c(v)\geq 0}$

この ILP は、問題 をカバーするための ILP のより一般的なクラスに属します。この ILP の整数ギャップはであるため、その緩和(変数が 0 または 1 のみである必要はなく、各変数が 0 から 1 の区間にあることを許可する) により、最小頂点カバー問題に対する因数近似アルゴリズムが得られます。さらに、その ILP の線形計画法緩和は半整数です。つまり、各エントリが 0、1/2、または 1 のいずれかである最適解が存在します。この分数解から、変数がゼロでない頂点のサブセットを選択することで、2 近似頂点カバーを取得できます。 ${\displaystyle 2}$${\displaystyle 2}$ ${\displaystyle x_{v}}$

頂点被覆問題の決定変種はNP完全であり、これは任意のグラフに対してこの問題を正確に解く効率的なアルゴリズムが存在する可能性が低いことを意味する。NP完全性は3-充足可能性からの還元によって証明されるか、Karpが行ったようにクリーク問題からの還元によって証明される。頂点被覆は立方体グラフ^[3]や次数が最大3の平面グラフでもNP完全のままである。^[4]

二部グラフの場合、ケーニッヒの定理によって記述される頂点カバーと最大マッチングの同値性により、二部頂点カバー問題を多項式時間で解くことができます。

ツリー グラフの場合、アルゴリズムはツリーの最初のリーフを見つけてその親を最小頂点カバーに追加し、リーフと親および関連するすべてのエッジを削除し、ツリーにエッジがなくなるまで繰り返し続けることで、多項式時間で最小頂点カバーを見つけます。

網羅的な探索アルゴリズムは、時間 2 ^k n ^{O (1)}で問題を解くことができます。ここで、k は頂点カバーのサイズです。したがって、頂点カバーは固定パラメータで扱いやすく、小さなkにのみ関心がある場合は、多項式時間で問題を解くことができます。ここで機能するアルゴリズム手法の 1 つは、制限付き探索木アルゴリズムと呼ばれ、そのアイデアは、いくつかの頂点を繰り返し選択して再帰的に分岐し、各ステップで 2 つのケース、つまり現在の頂点またはそのすべての隣接頂点を頂点カバーに配置するというものです。パラメータに対する最良の漸近依存性を達成する頂点カバーを解くアルゴリズムは、時間 で実行されます。^[5]この時間制限のklam値(妥当な時間で解くことができる最大のパラメータ値の推定値) は約 190 です。つまり、追加のアルゴリズムの改善が見つからない限り、このアルゴリズムは頂点カバー数が 190 以下のインスタンスにのみ適しています。合理的な複雑性理論的仮定、すなわち指数時間仮説の下では、の場合でも実行時間を 2 ^{o ( k )}に改善することはできません。 ${\displaystyle O(1.2738^{k}+(k\cdot n))}$${\displaystyle n}$${\displaystyle O(k)}$

しかし、平面グラフ、およびより一般的には、マイナーとしていくつかの固定グラフを除いたグラフの場合、サイズkの頂点カバーは時間で見つかります。つまり、問題は指数関数的に固定パラメータで処理可能です。^{[6]このアルゴリズムは、}指数時間仮説の下では、平面グラフ上の頂点カバーを時間で解くアルゴリズムがないという意味で、再び最適です。^[7]${\displaystyle 2^{O({\sqrt {k}})}n^{O(1)}}$${\displaystyle 2^{o({\sqrt {k}})}n^{O(1)}}$

辺の両端点を頂点カバーに繰り返し取り入れ、グラフから削除することで、係数 2 の近似値を求めることができます。言い換えると、貪欲アルゴリズムを使用して最大マッチングM を見つけ、 M内の辺のすべての端点で構成される頂点カバーCを構築します。次の図では、最大マッチングM は赤でマークされ、頂点カバーCは青でマークされています。

このように構築された集合C は頂点カバーです。辺e がCによってカバーされていないと仮定すると、M  ∪ { e } はマッチングであり、e  ∉  Mとなり、これはMが最大であるという仮定と矛盾します。さらに、e  = { u ,  v } ∈ Mの場合、任意の頂点カバー（最適頂点カバーを含む）にはuまたはv（またはその両方）が含まれている必要があります。そうでない場合、辺eはカバーされません。つまり、最適カバーにはMの各辺の少なくとも1 つの端点が含まれます。全体として、集合C は最適頂点カバーの最大 2 倍の大きさになります。

この単純なアルゴリズムは、ファニカ・ガブリルとミハリス・ヤナカキスによって独立して発見されました。^[8]

より複雑な技術により、わずかに優れた近似係数を持つ近似アルゴリズムが存在することが示されています。たとえば、近似係数が の近似アルゴリズムが知られています。^[9]この問題は、密なグラフの近似係数で近似できます。 ^[10]${\textstyle 2-\Theta \left(1/{\sqrt {\log |V|}}\right)}$${\displaystyle 2/(1+\delta )}$${\displaystyle \delta }$

上記のアルゴリズムより優れた定数近似アルゴリズムは知られていない。最小頂点被覆問題はAPX 完全である。つまり、 P  =  NPでない限り、任意の適切な近似はできない。 PCP 定理の手法を使用して、DinurとSafra は2005 年に、 P  =  NPでない限り、十分に大きい頂点次数に対して最小頂点被覆を 1.3606 の係数内で近似できないことを証明した。^[11]その後、この係数は任意の に対して に改善された。^[12] さらに、ユニーク ゲーム予想が正しい場合、最小頂点被覆を 2 より適切な定数係数内で近似することはできない。^[13]${\displaystyle {\sqrt {2}}-\epsilon }$${\displaystyle \epsilon >0}$

前述のように、最小サイズの頂点カバーを見つけることは最大サイズの独立集合を見つけることと同等ですが、近似値を保存する点では 2 つの問題は同等ではありません。独立集合問題には、 P  =  NPでない限り、定数係数近似値はありません。

近似-頂点-被覆( G ) 
C = ∅ E ' = G . E  
 

E ' ≠ ∅の場合、( u , v )をE 'の任意の辺とするC = C ∪ { u , v } E 'からuまたはvに接続するすべての辺を削除する   
            
         
              

リターンC 

^{[14] [15]}

頂点被覆最適化は、多くの現実世界および理論上の問題のモデルとして機能します。たとえば、フロア内のすべての部屋 (ノード) を接続するすべての廊下 (エッジ) をカバーする閉回路カメラをできるだけ少なく設置することに関心のある商業施設は、その目的を頂点被覆最小化問題としてモデル化できます。この問題は、合成生物学および代謝工学アプリケーションでの反復 DNA 配列の除去をモデル化するためにも使用されています。^{[16] [17]}

• 支配的なセット

ウィキメディア・コモンズには、頂点被覆問題に関連するメディアがあります。

• Weisstein、Eric W.「頂点カバー」。MathWorld。
• Weisstein、Eric W.「最小頂点カバー」。MathWorld。
• Weisstein、Eric W.「頂点被覆数」。MathWorld。
• 川の渡り（とアルクイン数） – Numberphile