在多项式时间内寻找最大团体的顶点

假设你有一个黑盒子，它可以在不变的时间内解决团体问题。在多项式时间内寻找最大团体的顶点

给黑箱一个带有界限k的无向图G，它输出“是”或“否”，图G有一个至少有k个顶点的团。

你会如何使用这个黑匣子在多项式时间内找到最大派系的顶点？

2014-11-03 Grib

这听起来很像家庭作业 - 它应该被标记为家庭作业。 – Kaganar 2014-11-03 18:27:51

明显的作业，没有尝试解决方案 - >投票结束为“太广泛”。 – 2014-11-03 18:31:03

我不是要求一个完整的解决方案，只是一些帮助如何开始。标记为家庭作业是什么意思？它说作业标签是不允许的。 – Grib 2014-11-03 18:43:24

作为一个提示，想想如果从图中选择一个节点，删除它，然后检查是否还有k-clique会发生什么。黑匣子会说有或没有。如果还有一个K集团，你会学到什么？如果没有，你会学到什么？

希望这有助于！

2014-11-03 19:03:08 templatetypedef

我看到了，你是说你需要做的就是从图形中删除一个节点，将图形重新插入黑盒并再次测试？因此，以这种方式删除导致yes-> no change的每个节点都是属于最大集团一部分的节点，否则不是。 – Grib 2014-11-03 20:02:49

回答