# 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. Aug 22, 2011 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. Aug 22, 2011 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. Aug 22, 2011 at 15:43
• when you say 'edge-disjunctive' do you really mean 'edge-disjoint' ? Aug 22, 2011 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$? Aug 22, 2011 at 21:53