# Does there exist polytime algorithm for this partitioning problem?

I would like to know if there exists a polytime probablistic algorithm for the problem described below. It is relevant for construction of a crossvalidation-partitioning in statistics, fulfilling certain constraints.

Or is it maybe NP-complete? I don't see any direct connections to any NP-complete problem I know of.

Input: $(N,K, (\phi_1, \ldots, \phi_l))$

Informal description:

Let $\{1 \ldots N\}$ be partitioned according to functions $\phi_1, \ldots, \phi_l$. Find a random partition $\Phi : \{1\ldots N\} \rightarrow \{1\ldots K\}$ s.t. for all $i$, elements with the same value under $\phi_i$, will get at least 2 different values under $\Phi$. Furthermore, the new partitioning should be balanced.

If no solution exists, halt with error.

Formal description:

Let $N, K \in \mathbb N$, and $\phi_i : \{1 \ldots N\} \rightarrow \{1 \ldots m_i\}$ be given for $i \in \{1 \ldots l\}$.

Find a random $\Phi : \{1\ldots N\} \rightarrow \{1\ldots K\}$ s.t. $$\forall i\in \{1 \ldots l\} :\forall v \in \{1\ldots m_i\} : |\Phi( \phi_i^{-1}(v) )| \geq 2$$ $$\forall v \in \{1\ldots K\} :\left\lfloor \frac{N}{K} \right\rfloor \leq |\Phi^{-1}(v)| \leq \left\lceil \frac{N}{K} \right\rceil$$

• Stating that the result must be “random” is not the right way to specify a constraint. Surprisingly it is explained in Dilbert: dilbert.com/strips/comic/2001-10-25 – Tsuyoshi Ito May 7 '11 at 15:50
• I write "random", since I desire the following property: If there exists more than one solution, the algorithm should output any of these with equal probability. But anyways -- I would also be interested to know if there exists an algorithm without this property. – Søren Haagerup May 7 '11 at 15:57
• You mean "nondeterministic" instead of "random". But simply writing "some" instead of "random" would do the trick. – Dave Clarke May 7 '11 at 17:49
• There is absolutely nothing wrong with considering the problem of randomly sampling amongst the partitions with the properties above. But then the correct terminology would be asking for NP-hardness, not NP-completeness. – Kristoffer Arnsfelt Hansen May 8 '11 at 18:33

(This is about the problem in which $|\phi(\Phi^{-1}(i))|\geq 2$ instead of $|\Phi(\phi^{-1}(i))|\geq 2$. Read it too fast. On the bright side Dave fixes it in a comment to this message )

What about saying it computes a proper edge coloring of a regular graph ? This problem is NP-Complete, and amounts, given a graph as an entry, to find a partition of its edges into matchings.

Vizing's theorem says that to do that Delta (the maximum degree of your graph) or Delta + 1 colors are required, though deciding which is NP-hard.

In your case, I think setting $N$ to the be number of edges, and setting K to Delta would do the trick. You then want to split your $N$ edges into $K=\Delta$ classes, and N is a multiple of Delta (for example in 3-regular graphs, for which the problem is still NP-hard).

In order to ensure that the answer is a proper edge coloring, one can let $\phi_v$ (for each vertex $v$) be the function equal to $0$ when edge $e\in [N]$ is adjacent to $v$, and 1 otherwise. If each color class has at least two different images for each $\phi_v$, it means that each color class contains a edge incident to each vertex. As the graph is Delta-regular, it also means that all the edges around a vertex have different colors as there are only Delta edges around each vertex, and if a class had two it means one would have none.

If it's true it would mean that finding one answer to your question is hard, and sampling solutions too :-)

Nathann

• Under this reduction, each vertex would only need to be incident on edges with two colors. I think this would work with $|E|\cdot\binom{\Delta}{2}$ functions $\phi_i$, one for every two edges incident on the same vertex. Give these two edges value 0 and all others 1, and now $\Phi$ has to color these two edges differently. As this is true for every pair of edges incident on the same vertex, $\Phi$ is a valid coloring. – Dave May 7 '11 at 17:31
• Arggg !! I had read $\phi(\Phi^{-1}(v))$ instead of what is written ! – Nathann Cohen May 7 '11 at 17:56
• Ok, after re-reading several times I'm both confident your technique works and also that I didn't make any other mistake reading the problem ! Thank you ! :-) – Nathann Cohen May 7 '11 at 18:01
• I'm convinced that it's NP-complete now, thank you :-). I also think it's possible to reduce equitable coloring to an instance of this. – Søren Haagerup May 7 '11 at 19:46