<p>Given an undirected graph $G=(V,E)$ with a color on each edge, the problem is to find a 2-partition $(V_1,V_2)$ of $V$ s.t. the number of colors used by the edges $uv, u \in V_1, v \in V_2$ is minimized. </p>

<p>For example, a cut with 1 blue edge, 1 red edge, and 1 yellow edge between $V_1$ and $V_2$ is worst than a cut with 10 blue edges and 15 red edges between $V_1$ and $V_2$. </p>

<p>Of course, the uncolored cut is well-known to be polynomial-time solvable. The complexity of this colored version is reported as an open-problem in <a href="http://hal.archives-ouvertes.fr/hal-00371100/en" rel="noreferrer">http://hal.archives-ouvertes.fr/hal-00371100/en</a>. It surprise me. Do I miss some known result?</p>

CC BY-SA 3.0
2012-01-12T16:14:38.883Z
What is exactly the function that is used to calculate the cost of the cut? (is it equal to the number of colors involved in the cut?)
Marzio De Biasi
CC BY-SA 3.0
2012-01-12T16:23:02.217Z
@Vor : exactly.
richard
CC BY-SA 3.0
2012-01-12T17:38:57.433Z
is the number of colours fixed? If it is, then the question is poly-time solvable, but the most obvious approach has a factor of $k!$ where $k$ is the number of colours.
Artem Kaznatcheev
CC BY-SA 3.0
2012-01-12T17:53:43.067Z
I am not sure what the approach that has a factor of $k!$ is, but it's easy to get an algorithm that depends on $k$ as $2^k$: guess the colors in the optimal solution, set the edges with the guessed colors to have weight 0 and the edges with the remaining colors to have infinite weight, and run a min cut algorithm.
Sasho Nikolov
CC BY-SA 3.0
2012-01-13T11:54:43.087Z
What is the constraint on the cut?  Is it just neither V1 nor V2 can be empty, or does it have to be an (s,t)-cut for some given vertices s and t?  (Needless to say, if there is no constraint, setting V1=∅ and V2=V is trivially optimal.)
Tsuyoshi Ito
CC BY-SA 3.0
2012-01-13T12:45:06.603Z
@ArtemKaznatcheev: Unbounded.
richard
CC BY-SA 3.0
2012-01-13T12:45:51.643Z
@TsuyoshiIto: Yep, non-empty sets
richard
CC BY-SA 3.0
2012-01-15T15:11:32.070Z
the s-t minimum color cut is NP-Hard... from set cover problem.. and if using each color separately if there is exactly one non-trivial connected component each time (with size more than 1) then it is in P...
singhsumit
CC BY-SA 3.0
2012-01-19T16:48:29.467Z
is it not equivalent to find min-cut in hyper-graphs? Then the problem is in P.
singhsumit
<ds.algorithms><reference-request><graph-algorithms><open-problem>
Complexity of the min edge-colored cut problem
richard
# Complexity of the min edge-colored cut problem

(Asked by: username_0 on 2012-01-12)

Given an undirected graph $G=(V,E)$ with a color on each edge, the problem is to find a 2-partition $(V\_1,V\_2)$ of $V$ s.t. the number of colors used by the edges $uv, u \in V\_1, v \in V\_2$ is minimized.

For example, a cut with 1 blue edge, 1 red edge, and 1 yellow edge between $V\_1$ and $V\_2$ is worst than a cut with 10 blue edges and 15 red edges between $V\_1$ and $V\_2$.

Of course, the uncolored cut is well-known to be polynomial-time solvable. The complexity of this colored version is reported as an open-problem in <http://hal.archives-ouvertes.fr/hal-00371100/en>. It surprise me. Do I miss some known result?

**Tags:** ds.algorithms, reference-request, graph-algorithms, open-problem
> **Comments:**
> **username_1**: What is exactly the function that is used to calculate the cost of the cut? (is it equal to the number of colors involved in the cut?)  
> **username_0**: @Vor : exactly.  
> **username_2**: is the number of colours fixed? If it is, then the question is poly-time solvable, but the most obvious approach has a factor of $k!$ where $k$ is the number of colours.  
> **username_3**: I am not sure what the approach that has a factor of $k!$ is, but it's easy to get an algorithm that depends on $k$ as $2^k$: guess the colors in the optimal solution, set the edges with the guessed colors to have weight 0 and the edges with the remaining colors to have infinite weight, and run a min cut algorithm.  
> **username_4**: What is the constraint on the cut?  Is it just neither V1 nor V2 can be empty, or does it have to be an (s,t)-cut for some given vertices s and t?  (Needless to say, if there is no constraint, setting V1=∅ and V2=V is trivially optimal.)  
> **username_0**: @ArtemKaznatcheev: Unbounded.  
> **username_0**: @TsuyoshiIto: Yep, non-empty sets  
> **username_5**: the s-t minimum color cut is NP-Hard... from set cover problem.. and if using each color separately if there is exactly one non-trivial connected component each time (with size more than 1) then it is in P...  
> **username_5**: is it not equivalent to find min-cut in hyper-graphs? Then the problem is in P.  

---

## 0 answers

