这个最大clique多项式时间方法的缺陷？

Question

我一直试图用下面提到的算法解决最大团问题,到目前为止还没能找到失败的情况.
算法:
对于给定的图,每个节点编号从1到N.
1.将一个节点视为永久节点并形成一组节点,使每个节点连接到该永久节点.(该集合还包括永久节点)
2现在形成原始图形的子图,使其包含所形成的集合中的所有节点,并且仅包含集合中存在的节点之间的那些边缘.
3.找出每个节点的度数.
如果所有节点都有相同的学位,那么我们就有了一个集团.
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,而其他clique节点具有度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}}