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 (Grtschel, 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)
Complexity of finding weighted edge-disjunctive triangles in a graph
cc.complexity theory;graph theory