<p><em>(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 )</em></p>

<p>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.</p>

<p>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.</p>

<p>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).</p>

<p>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.</p>

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

<p>Nathann </p>

CC BY-SA 3.0
2011-05-07T17:31:13.173Z
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
CC BY-SA 3.0
2011-05-07T17:56:32.597Z
Arggg !! I had read $\phi(\Phi^{-1}(v))$ instead of what is written !
Nathann Cohen
CC BY-SA 3.0
2011-05-07T18:01:37.430Z
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
CC BY-SA 3.0
2011-05-07T19:46:11.570Z
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
CC BY-SA 3.0
2011-05-07T16:50:52.277Z
2011-05-07T18:24:37.720Z
2011-05-07T18:24:37.720Z
Nathann Cohen
<p>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.</p>

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

<p><strong>Input:</strong> $(N,K, (\phi_1, \ldots, \phi_l))$</p>

<p><strong>Informal description:</strong></p>

<p>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.</p>

<p>If no solution exists, halt with error.</p>

<p><strong>Formal description:</strong></p>

<p>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\}$.</p>

<p>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
$$</p>

CC BY-SA 3.0
2011-05-07T15:50:25.527Z
Stating that the result must be “random” is not the right way to specify a constraint.  Surprisingly it is explained in Dilbert: http://www.dilbert.com/strips/comic/2001-10-25/
Tsuyoshi Ito
CC BY-SA 3.0
2011-05-07T15:57:57.347Z
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
CC BY-SA 3.0
2011-05-07T17:49:17.067Z
You mean "nondeterministic" instead of "random". But simply writing "some" instead of "random" would do the trick.
Dave Clarke
CC BY-SA 3.0
2011-05-08T18:33:39.837Z
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
<cc.complexity-theory><np-hardness><application-of-theory><randomized-algorithms>
Does there exist polytime algorithm for this partitioning problem?
Søren Haagerup
# Does there exist polytime algorithm for this partitioning problem?

(Asked by: username_0 on 2011-05-07)

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
$$

**Tags:** cc.complexity-theory, np-hardness, application-of-theory, randomized-algorithms
> **Comments:**
> **username_1**: Stating that the result must be “random” is not the right way to specify a constraint.  Surprisingly it is explained in Dilbert: http://www.dilbert.com/strips/comic/2001-10-25/  
> **username_0**: 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.  
> **username_2**: You mean "nondeterministic" instead of "random". But simply writing "some" instead of "random" would do the trick.  
> **username_3**: 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.  

---

## 1 answers

### Answer by username_4 on 2011-05-07. Score: 6 | Accepted answer

*(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

> **Comments:**
> **username_5**: 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.  
> **username_4**: Arggg !! I had read $\phi(\Phi^{-1}(v))$ instead of what is written !  
> **username_4**: 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 ! :-)  
> **username_0**: 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.  

---

