6
$\begingroup$

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)

Improve this question
$\endgroup$
9
  • 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, 2011 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, 2011 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, 2011 at 15:43
  • 4
    $\begingroup$ when you say 'edge-disjunctive' do you really mean 'edge-disjoint' ? $\endgroup$
    – Suresh Venkat
    Aug 22, 2011 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, 2011 at 21:53

1 Answer 1

Reset to default
6
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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