13
$\begingroup$

There are $n$ bins, the $i$th bin contain $a_i$ balls. The balls has $n$ colors, there are $a_i$ balls of color $i$. Let $m=\sum_{i=1}^n a_i$.

A swap is take a ball from one bin and swap with a ball from another bin. We want minimum number of swaps such that each bin only contain balls with the same color.

I know a easy special cases $a_i\leq 2$ for all $i$. (If $a_i=2$ for all $i$, then you can even do it by swapping each ball at most once.)

Edit: This is wrong because finding $c(D)$ is NP-hard.

If we know which color goes to which bin, the problem is easy.

Consider a multi-digraph $D=(V,A)$, $V=\{v_1,\ldots,v_n\}$. If we know color $i$ goes to bin $b(i)$, then there are $k$ parallel arcs $(j,b(i))$ in $A$ iff bin $j$ contains $k$ balls of color $i$. Each component of the graph is Eulerian. The minimum number of swaps required is $m-c(D)$, where $c(D)$ is the number of arc disjoint cycles that covers $A$. We can swap by "following" a Eulerian circuit. (a swap using an arc of a minimal cycle can change it to a smaller minimal cycle and a self loop). Once the entire graph is set of self loops, we have made all the necessary swaps.

How hard is this problem in general?

$\endgroup$

1 Answer 1

3
$\begingroup$

Maximal decomposition of an Eulerian directed graph into edge disjoint cycles is NP-Hard, at least according to this book: Algorithms and Applications: Essays Dedicated to Esko Ukkonen on the Occasion of His 60th Birthday.

btw, here is an article which is relevant to the problem you seem to be trying to solve: Asymptotically optimal algorithm for the Dutch National flag algorithm.

For $n \le 6$, the paper gives a simple algorithm.

$\endgroup$
1
  • $\begingroup$ I incorrectly assumed we can find a maximal decomposition by just walking on the graph until it hits a cycle, and start again. So indeed this problem is NP-hard in general. $\endgroup$
    – Chao Xu
    Jun 12, 2013 at 2:22

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.

Not the answer you're looking for? Browse other questions tagged or ask your own question.