我寻找最大独立集的贪心方法是最优的吗？

Question

我正在执行一项任务，以找到图中最大的独立集。在研究了各种方法之后，我发现回溯经常被推荐，但它具有指数时间复杂度，导致状态空间显着增长。

为了优化我的解决方案，我实现了一种略有变化的贪婪方法。我使用邻接列表表示该图，并按顶点的入度降序对顶点进行排序。我的流程如下：

1.选择入度最大的顶点。 2.从图中删除该顶点（及其边）。 3.重复这个过程，直到没有顶点为止。

我一直使用这种方法获得我认为的最佳解决方案，并且它的执行速度比回溯更快。但是，我很好奇是否有任何反例可以证明我的方法不是最佳的。

我寻找最大独立集的贪心方法是否合理，或者是否存在无法提供最优解的特定情况？ 谁能提供一个反例，说明我的方法产生了次优的独立集？

我尝试了多个例子。常规贪婪的反例在这里不起作用。它找到了最佳的。

帮我找一个反例。

Answer 1

贪婪方法是一种很好的启发式方法，但首先删除排名最高的节点有时可能会阻碍找到最佳解决方案。例如，考虑节点 N1 到 N6 具有以下邻接矩阵：

N1 N2 N3 N4 N5 N6
0  1  1  1  0  0
1  0  0  0  1  0
1  0  0  0  0  1
1  0  0  0  0  0
0  1  0  0  0  0
0  0  1  0  0  0

这里最大的独立集是N1，N5，N6。如果用贪心法去掉N1，就找不到最优解。因此，具有最高边度的节点也可能是最佳独立集的一部分。