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

<p>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.</p>

<p>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.</p>

CC BY-SA 3.0
2011-08-22T21:58:32.787Z
2011-08-22T21:58:32.787Z
David Eppstein
<p>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 <em>valid</em>, iff two edges have positive weight and one edge has negative weight. </p>

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

<p><strong>Background:</strong> 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.)</p>

<p>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)</p>

CC BY-SA 3.0
2011-08-22T13:37:03.113Z
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
CC BY-SA 3.0
2011-08-22T14:48:25.163Z
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
CC BY-SA 3.0
2011-08-22T15:43:18.353Z
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
CC BY-SA 3.0
2011-08-22T16:03:13.747Z
Oh, I was a little bit slow on that. Sorry. The question has now been edited.
Florian Jaehn
CC BY-SA 3.0
2011-08-22T16:28:49.540Z
when you say 'edge-disjunctive' do you really mean 'edge-disjoint' ?
Suresh Venkat
CC BY-SA 3.0
2011-08-22T19:32:24.990Z
I fear that I have to acknowledge my ignorance. Both words translate to German word "disjunkt". What I want to say is: In $S$, there must not be any two triangles that share a common edge.
Florian Jaehn
CC BY-SA 3.0
2011-08-22T21:53:38.100Z
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
CC BY-SA 3.0
2011-08-22T22:44:05.710Z
Oops sorry, we want edge-disjoint triangles rather than vertex-disjoint triangles, like in 3D matching.
Andrew D. King
CC BY-SA 3.0
2011-08-23T01:41:02.657Z
@Andrew: I had up-voted your comment without realizing the difference between edge-disjoint and vertex-disjoint triangles.  Anyway, I think that if you start with the [Latin square completion problem](http://en.wikipedia.org/wiki/Latin_square#Mathematical_puzzles) instead of 3-dimensional matching, you get a reduction to the current problem with edge-disjoint triangles.
Tsuyoshi Ito
<cc.complexity-theory><graph-theory>
Complexity of finding weighted edge-disjunctive triangles in a graph
Florian Jaehn
# Complexity of finding weighted edge-disjunctive triangles in a graph

(Asked by: username_0 on 2011-08-22)

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)

**Tags:** cc.complexity-theory, graph-theory

> **Comments:**
> **username_1**: 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.  
> **username_0**: 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.  
> **username_1**: 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.  
> **username_0**: Oh, I was a little bit slow on that. Sorry. The question has now been edited.  
> **username_2**: when you say 'edge-disjunctive' do you really mean 'edge-disjoint' ?  
> **username_0**: I fear that I have to acknowledge my ignorance. Both words translate to German word "disjunkt". What I want to say is: In $S$, there must not be any two triangles that share a common edge.  
> **username_3**: 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$?  
> **username_3**: Oops sorry, we want edge-disjoint triangles rather than vertex-disjoint triangles, like in 3D matching.  
> **username_1**: @Andrew: I had up-voted your comment without realizing the difference between edge-disjoint and vertex-disjoint triangles.  Anyway, I think that if you start with the [Latin square completion problem](http://en.wikipedia.org/wiki/Latin_square#Mathematical_puzzles) instead of 3-dimensional matching, you get a reduction to the current problem with edge-disjoint triangles.  

---

## 1 answers

### Answer by username_4 on 2011-08-22. Score: 6

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.


---

