这个图有多难？

Question

我有一个问题需要解决一个社交网络应用程序,这听起来很难:我不确定它的NP完整与否.它闻起来可能是NP完全的,但我对这些东西没有很好的意识.在任何情况下,算法对我来说都是更好的消息.

无论如何,输入是一些图形,我想要做的是将节点分成两组,以便两组都不包含三角形.如果它有帮助,我知道这个特殊的图形是3可着色的,虽然我实际上并不知道着色.

启发式地,一个"贪婪"的算法似乎很快收敛:我只是在分区的任何一侧寻找三角形,并在找到它们时打破它们.

Answer 1

我的答案是错误的

我会继续讨论。请不要投反对票，这个想法可能仍然有帮助。

我认为它是 NP 难的，因为用 4 种颜色对 3 种可着色图进行着色是 NP 难的（论对 3 种可着色图进行 4 种着色的硬度）。

我们给出了一个新的证明，表明仅使用四种颜色对 3 色图进行着色是 NP 困难的。这个结果是已知的，但我们的证明是新颖的，因为 [...]

假设我们可以在多项式时间内将一个 3 色图划分为 2 个集合 A、B，使得两者都没有三角形。然后我们可以如下解决4色：

• 颜色组 A 带有 C1、C2，颜色组 B 带有 C3、C4。
• 每组都是 2 色的，因为它没有三角形<- 这是我错的地方
• 2 色可 2 色图是多项式
• 然后我们在多项式时间内对可 3 色的图进行 4 色着色

通过这种减少，我声称你所做的事情一定是 NP 难的。