頂点カバーの近似アルゴリズム

Question

PがNPと等しくない場合、kが固定定数である最適な頂点カバーのkに含まれる近似アルゴリズムがないことが分かりますか？

Answer 1

質問が相加的なエラーで理解される場合、そのようなアルゴリズムは存在しません。矛盾を狙って、Aがそのようなアルゴリズムであると仮定します。これはA(G)がAとtau(G)によって生成Gの頂点カバーのカーディナリティである任意のグラフG、

A(G) <= tau(G) + k 

が成立する、の最小頂点被覆の基数を表すように、非負整数kがあることを意味します。前述のアルゴリズムの存在に関して最小値としてkを選択する。特に、k => 1がある。そうでなければ、頂点カバー問題は多項式時間で解くことができ、P=NPが成り立たなければ不可能であるからである。

Gを仲裁グラフにする。 k+1同形コピーGを取ってグラフG'を作成します。

tau(G') = (k + 1) tau(G) 

が成り立ちます。さらに、以下を得る。

A(G') <= tau(G) + k 
     = (k + 1) tau(G) + k 

G*はAによって生成された最小の頂点カバーとG'にGの同型コピーとします。この頂点カバーのサイズをA(G*)とする。矛盾を狙って、

A(G*) >= tau(G*) + k 

とする。これは、k > 0が成立するので、

A(G') >= (k + 1) A(G*) 
     >= (k + 1) (tau(G*) + k) 
     = (k + 1) (tau(G) + k) 
     = (k + 1) tau(G) + k + k^2 
     > (k + 1) tau(G) + k 

が成り立つことを意味します。これは、近似の品質との矛盾であるAです。これは、

A(G*) < tau(G*) + k 

が成立することを意味します。 tau(G*) = tau(G)が保持しているように、これは我々がkを最小限に選ばれた、すべての建設手順は、A内で行うことができるので、矛盾である

tau(G) + k 

より厳密に小さいカーディナリティとGの頂点被覆を生成するためにAを使用していることを意味し多項式で結び付けられた実行時間が得られ、結果として多項式で境界付けられた実行時間境界が得られる。