10
$\begingroup$

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?

Improve this question
$\endgroup$
9
  • 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$
    – Marzio De Biasi
    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$
    – Artem Kaznatcheev ♦
    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$
    – Sasho Nikolov
    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$
    – Tsuyoshi Ito
    Jan 13, 2012 at 11:54

0

Reset to default

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.