線形計画法を用いた最小頂点カバーアルゴリズム

Question

次のアルゴリズムを考慮してください。 $ g $ を指定して、 $ n $ vistices、設定各頂点 $ v_i $の変数 $ x_i $ がある線形プログラミングの問題 lp $ g $ の各変数は、値 $ \ geq 0 $ を取ることができます。エッジ $ g $ の$ v_av_b $ constraint $ X_A + X_B \ GEQ 1 $ 。目的関数は $ \ min \ sum \ limits_ {1} ^ {n} {x_i} $ です。 $ 0 $ に設定されていない変数の中で、変数（または変数の1つ）を見つけます。 $ x_i $ 。 $ 0 $ に設定すると、目的関数の最小値が与えられます。 constraint $ x_i= 0 $ を lp に追加します。 lp の最適解が整数（つまり、 $ \ left \ {0; 1 \ right \};};; ）

lp の最終的な最適解の値で、値 $ 1 $ に関連付けられている頂点を探しています。 $ G $ の最小頂点カバーではありません（存在する場合）。

Answer 1

グラフを考慮してください

  2-4---7
 /  |\ /|
1   | × |
 \  |/ \|
  3-5---6

.

設定 $ x_1、x_2、x_3、x_6 $ または $ x_7 $ あなたのLPを与える $ x_4 $ 、または $ x_5 $ を0に設定しながら4の値は、LPの値を示します。5.ただし、 $ x_1= 0 $ を設定した場合、最終的な頂点カバーはサイズ4のサイズ5の頂点カバーを取得します。P>