algorithm - 这种最大集团多项式时间方法有缺陷吗？

Question

我一直在尝试用下面提到的算法解决最大团问题，但到目前为止还没有找到它失败的情况。
算法:
对于给定的图，每个节点编号从 1 到 N。
1. 把一个节点看成永久节点，形成一个节点集合，使得每个节点都连接到这个永久节点。(这个集合也包括永久节点)
2. 现在形成原始图的子图，使其包含形成的集合中的所有节点，并且仅包含集合中存在的节点之间的那些边。
3.求每个节点的度数。
4. 如果所有节点的度数都相同，则我们有一个集团。
5. 否则从该子图中删除度数最小的节点并从步骤 3 开始重复。
6. 对图中的所有节点重复步骤 1-5。

谁能指出这个算法的缺陷？
这是我的代码 http://pastebin.com/tN149P9m .

Answer 1

这是一系列反例。从 k-clique 开始。对于这个集团中的每个节点，将其连接到 K_{k-1,k-1} 的新副本的每个节点，即 k-1 加上 k-1 个节点上的完整二分图。对于团中的每个永久节点，残差图是其 K_{k-1,k-1} 和团的副本。 K_{k-1,k-1}中节点的度数为k，其他团节点的度数为k - 1，因此后者被删除。

这是一个 16 节点的反例，通过设置 k = 4 并识别环中 K_{3,3} 的部分获得:

{0: {1, 2, 3, 4, 5, 6, 7, 8, 9},
 1: {0, 2, 3, 7, 8, 9, 10, 11, 12},
 2: {0, 1, 3, 10, 11, 12, 13, 14, 15},
 3: {0, 1, 2, 4, 5, 6, 13, 14, 15},
 4: {0, 3, 7, 8, 9, 13, 14, 15},
 5: {0, 3, 7, 8, 9, 13, 14, 15},
 6: {0, 3, 7, 8, 9, 13, 14, 15},
 7: {0, 1, 4, 5, 6, 10, 11, 12},
 8: {0, 1, 4, 5, 6, 10, 11, 12},
 9: {0, 1, 4, 5, 6, 10, 11, 12},
 10: {1, 2, 7, 8, 9, 13, 14, 15},
 11: {1, 2, 7, 8, 9, 13, 14, 15},
 12: {1, 2, 7, 8, 9, 13, 14, 15},
 13: {2, 3, 4, 5, 6, 10, 11, 12},
 14: {2, 3, 4, 5, 6, 10, 11, 12},
 15: {2, 3, 4, 5, 6, 10, 11, 12}}