关于最大独立集松弛问题及其对偶规划的疑问

嘿，我来帮你理清这里的逻辑，解决你遇到的困惑：

1. LP松弛的边界问题：为什么必须加上 $x_v\leq1$？ #

你观察得非常准确——如果只把整数约束放松成 $x_v\geq0$，当图里存在孤立顶点时，这个LP松弛确实会变成无界的：孤立顶点没有任何边约束限制，$x_v$ 可以无限增大，目标函数自然趋向无穷大，这显然不符合我们对松弛问题的预期（松弛应该是原整数规划的有界上界）。

那些只写 $x_v\geq0$ 的资料，要么是默认讨论的图没有孤立顶点，要么是为了简化表述省略了$x_v\leq1$——但严格来说，标准的LP松弛必须明确写出 $0\leq x_v\leq1$，这样才能覆盖所有图的场景，保证松弛问题有界且合理。

2. 对偶模型的额外变量与最小边覆盖的关系 #

先纠正你对偶模型里的一个小笔误：你写的 $y_v\geq1$ 应该是 $y_v\geq0$（因为我们加的是 $x_v\leq1$ 的不等式约束，对应的对偶变量是非负的）。修正后的对偶模型如下：
$$
\begin{align*}
&\min\sum_{e\in E}y_{e}+\sum_{v\in V}y_v\
&\text{s.t } \sum_{e\in E\colon v\in e} y_{e} + y_v \geq 1 &\text{for all }v\in V\
&\quad\quad y_e\geq 0, \text{ for all }e\in E\
&\quad\quad y_v\geq 0, \text{ for all }v\in V
\end{align*}
$$

至于你提到的“这个复杂的对偶模型和‘最大独立集的对偶是最小边覆盖’的经典结论冲突”，其实核心原因是经典结论是基于无孤立顶点的图场景：

• 当图中没有孤立顶点时，每个顶点都至少有一条边相连，此时在对偶模型的最优解里，所有 $y_v$ 都会取0——因为通过边变量 $y_e$ 就能满足 $\sum_{e\ni v}y_e\geq1$ 的约束，不需要启用额外的 $y_v$。这时对偶模型就退化为最小边覆盖的标准模型：
  $$
  \begin{align*}
  &\min\sum_{e\in E}y_{e}\
  &\text{s.t } \sum_{e\in E\colon v\in e} y_{e} \geq 1 &\text{for all }v\in V\
  &\quad\quad y_e\geq 0, \text{ for all }e\in E
  \end{align*}
  $$
• 而当图中有孤立顶点时，这些顶点没有边相连，约束就变成 $y_v\geq1$，在最小化目标函数时，$y_v$ 会取1——这其实对应了“边覆盖无法覆盖孤立顶点，必须单独处理”的情况，是对经典边覆盖模型的合理扩展，而不是矛盾。

所以本质上，你的困惑来自于资料表述的严谨性差异，以及是否覆盖孤立顶点场景的区别。严格的LP松弛必须包含 $0\leq x_v\leq1$，而对偶模型的额外变量只是对特殊场景的补充，在经典场景下会自然退化到我们熟悉的结论。

备注：内容来源于stack exchange，提问作者Proper Illumination