具有线性规划的最小顶点覆盖算法

Question

考虑以下算法：给定图 $ g $ 使用 $ n $ 顶点，设置线性编程问题 lp 在其中有一个变量 $ x_i $ ，每个顶点 $ v_i $ $ g $ ，每个变量可以取值 $ \ geq 0 $ ，每个边缘 $ v_av_b $ $ g $ 设置约束 $ X_A + X_B \ GEQ 1 $ 。目标函数是 $ \ min \ sum \ limits_ {1} ^ {n} {x_i} $ 。 查找变量（或变量之一） $ x_i $ ，其中变量未设置为 $ 0 $ ，设置为 $ 0 $ 提供目标函数的最小值。将约束 $ x_i= 0 $ 到 lp 。重复直到 lp 为整数的最佳解决方案（每个变量为 $ \ left \ {0; 1 \右\} $ ）。

我正在寻找一个图表，其中与在 lp 的最终最佳解决方案中占用的变量 $ 1 $ 的顶点不是 $ g $ 的最小顶点封面（如果存在）。

Answer 1

考虑图表

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

.

设置 $ x_1，x_2，x_3，x_6 $ 或 $ x_7 $ 到0给出您的lp值4，而设置 $ x_4 $ 或 $ x_5 $ to 0给出了您的lp值然而，如果设置 $ x_1= 0 $ ，则最终将获得大小5的顶点盖，而最佳顶点盖子大小为4。