2
$\begingroup$

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

Improve this question
$\endgroup$
4
  • 2
    $\begingroup$ 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 $\endgroup$
    – Tsuyoshi Ito
    Commented May 7, 2011 at 15:50
  • $\begingroup$ 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. $\endgroup$
    – Søren Haagerup
    Commented May 7, 2011 at 15:57
  • $\begingroup$ You mean "nondeterministic" instead of "random". But simply writing "some" instead of "random" would do the trick. $\endgroup$
    – Dave Clarke
    Commented May 7, 2011 at 17:49
  • $\begingroup$ 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. $\endgroup$
    – Kristoffer Arnsfelt Hansen
    Commented May 8, 2011 at 18:33

1 Answer 1

Reset to default
6
$\begingroup$

(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

Improve this answer
$\endgroup$
4
  • 1
    $\begingroup$ 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. $\endgroup$
    – Dave
    Commented May 7, 2011 at 17:31
  • $\begingroup$ Arggg !! I had read $\phi(\Phi^{-1}(v))$ instead of what is written ! $\endgroup$
    – Nathann Cohen
    Commented May 7, 2011 at 17:56
  • $\begingroup$ 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 ! :-) $\endgroup$
    – Nathann Cohen
    Commented May 7, 2011 at 18:01
  • $\begingroup$ 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. $\endgroup$
    – Søren Haagerup
    Commented May 7, 2011 at 19:46

Your Answer

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

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