algorithm - 这个图形问题有多难？

Question

我有一个社交网络应用程序的问题要解决，这听起来很难:我不确定它是否是 NP 完全的。听起来它可能是 NP 完全的，但我对这些东西没有很好的感觉。无论如何，算法对我来说是更好的消息。

无论如何，输入是一些图，我想做的是将节点分成两组，这样两组都不包含三角形。如果有帮助，我知道这个特定的图形是 3 色的，尽管我实际上不知道着色。

启发式地，“贪心”算法似乎收敛得很快:我只是在分区的任一侧寻找三角形，并在找到它们时将其打断。

Answer 1

问题的决策版本对于一般图是 NP-Complete:http://users.soe.ucsc.edu/~optas/papers/G-free-complex.pdf并且不仅适用于三角形。

当然，这仍然无助于解决搜索版本的三色图和三角形自由度问题(决策版本在 P 中很简单)。