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)

  • 3
    $\begingroup$ 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. $\endgroup$ – Tsuyoshi Ito Aug 22 '11 at 13:37
  • $\begingroup$ 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. $\endgroup$ – Florian Jaehn Aug 22 '11 at 14:48
  • 1
    $\begingroup$ 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. $\endgroup$ – Tsuyoshi Ito Aug 22 '11 at 15:43
  • 4
    $\begingroup$ when you say 'edge-disjunctive' do you really mean 'edge-disjoint' ? $\endgroup$ – Suresh Venkat Aug 22 '11 at 16:28
  • 2
    $\begingroup$ 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$? $\endgroup$ – Andrew D. King Aug 22 '11 at 21:53

Here's a reduction from edge coloring that I believe shows this to be NP-complete.

Let G,k be an instance of edge coloring: that is, we wish to know whether the edges of graph G can be colored with k colors. Make all edges in G negative, and add k new vertices to G, each connected by positive edges to every existing vertex in G.

Then, if G has an edge coloring, the modified graph has a set of edge-disjoint valid triangles that includes all of the edges in G: simply form a triangle connecting each edge in G to the new vertex that corresponds to its color. Conversely, if there exists a set of edge-disjoint valid triangles that includes all of the edges in G, then one can use the identities of the new vertices in each triangle as colors in an edge coloring of G.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.