# Complexity of finding weighted edge-disjunctive triangles in a graph

Given a simple graph, in which the edges are weighted with values from the set $\{-1,1\}$. Three pairwise adjacent edges define a triangle. A triangle is called valid, iff two edges have positive weight and one edge has negative weight.

Find a set $S$ of valid, edge disjunctive triangles, such that the cardinality of $S$ is maximized.

Background: An answer to the above question can be used to calcualte an upper bound for the Clique-Partitioning-Problem (Grötschel, Wakabayashi (1989): A CUTTING PLANE ALGORITHM FOR A CLUSTERING PROBLEM, Math. Prog.)

I assume that the problem is NP-complete. However, I failed to reduce "Independent set", "3D Matching", and "Partition into triangles" to the above problem. (Of course there still may be such reduction)

• What is the role of weight 0? Does it mean that the edge cannot be used in a valid triangle? If so, you are effectively not given a complete graph, but given an arbitrary graph with weights ±1. – Tsuyoshi Ito Aug 22 '11 at 13:37
• You are right, the problem is equivalent if an arbitrary graph with positive and negative weights is considered. The complete graph origins from the original problem. – Florian Jaehn Aug 22 '11 at 14:48
• I hoped that this would go without saying, but the reason I posted my previous comment is because your formulation of the problem was confusing to me. Please consider editing your question, because answering to a comment by posting another comment is only helpful to those who read comments. – Tsuyoshi Ito Aug 22 '11 at 15:43
• when you say 'edge-disjunctive' do you really mean 'edge-disjoint' ? – Suresh Venkat Aug 22 '11 at 16:28
• Can't you very easily reduce 3D matching to this problem by taking the 3D matching graph and making an edge negative precisely if it is between $V_1$ and $V_2$? – Andrew D. King Aug 22 '11 at 21:53