边双分割，没有三角形:复杂性？

Question

我必须找到一个算法来解决教职员工的问题。我不是在请求解决方案(请不要发布任何解决方案)，只需进一步阅读。

问题的答案是：

** Given a graph G = (V, E) find 2 sets S1 and S2 of edges of G such that:
   1. S1 ∪ S2 = E
   2. S1 ∩ S2 = ∅
   3. The 2 subgraphs of G formed by S1 and S2 do not contain triangles (triangle = 3 nodes such that they link together 2 by 2)

在过去的两天里，我一直在尝试寻找一个算法来解决这个问题，我认为我走在了正确的道路上。对于以前偶然发现它的任何人来说:你知道这个问题是否在多项式时间内得到了解决吗？(如果不是，是NP-complete/NP-hard/NP吗？)

先谢谢你，约翰

Answer 1

我又用谷歌搜索了一下，找到了。它被称为monochromatic triangle，它是NP完全的。