基于入度排序的贪心最大独立集算法是否最优？求反例

结论 #

该贪心算法无法保证得到最大独立集，存在明确的反例证明其只能得到次优解。

反例构造与验证 #

图结构 #

构造一个无向图，分为两个部分：

• 完全图K₄：包含顶点A、B、C、D，任意两个顶点间均有边连接。
• 独立集组：包含顶点S₁、S₂、S₃、S₄、S₅，其中：
  • S₁仅与A相连
  • S₂仅与B相连
  • S₃仅与C相连
  • S₄仅与D相连
  • S₅仅与A相连

顶点入度统计 #

• A的入度为5（连接B、C、D、S₁、S₅）
• B、C、D的入度均为4（连接K₄内3个顶点+1个对应S顶点）
• S₁~S₅的入度均为1

算法执行结果 #

1. 第一步选择入度最高的A，将其加入独立集，随后移除A及其所有邻接顶点（B、C、D、S₁、S₅）。
2. 剩余顶点S₂、S₃、S₄无相互连接，依次加入独立集。
3. 最终得到的独立集为{A, S₂, S₃, S₄}，大小为4。

最优独立集 #

选择所有S顶点{S₁, S₂, S₃, S₄, S₅}，这些顶点之间无任何边连接，构成大小为5的独立集——这是该图的最大独立集，明显优于算法输出的结果。

核心问题分析 #

你的贪心策略的缺陷在于：入度高的顶点通常关联大量低入度顶点，选择这类顶点会直接排除掉后续选择这些低入度顶点的可能，而这些低入度顶点的总数量可能远大于单个高入度顶点的贡献。由于最大独立集问题属于NP-hard问题，不存在多项式时间的贪心算法能确保全局最优，任何仅基于局部最优（如入度排序）的策略都会存在失效场景。

内容的提问来源于stack exchange，提问作者Sibi Varshan