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?

  • 1
    $\begingroup$ 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?) $\endgroup$ Jan 12, 2012 at 16:14
  • $\begingroup$ @Vor : exactly. $\endgroup$
    – richard
    Jan 12, 2012 at 16:23
  • $\begingroup$ 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. $\endgroup$ Jan 12, 2012 at 17:38
  • 3
    $\begingroup$ 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. $\endgroup$ Jan 12, 2012 at 17:53
  • $\begingroup$ 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.) $\endgroup$ Jan 13, 2012 at 11:54


Your Answer

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