# Complexity of the min edge-colored cut problem

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?

• 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?) Jan 12, 2012 at 16:14
• @Vor : exactly. Jan 12, 2012 at 16:23
• 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. Jan 12, 2012 at 17:38
• 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. Jan 12, 2012 at 17:53
• 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.) Jan 13, 2012 at 11:54