19
$\begingroup$

I am interested in the following problem: Given a set X and subsets X_1, ..., X_n of X, find a coloring of the elements of X with k colors such that the elements in each X_i are all differently colored. More specifically, I am looking at the case where all X_i are of size k. Is this known in the literature under some name? I am looking for characterizations of colorable instances and results on complexity (P vs. NP-hard). For example, for k=2, colorable instances correspond to bipartite graphs, and thus the problem can be solved in polynomial time.

Improve this question
$\endgroup$
2

4 Answers 4

Reset to default
15
$\begingroup$

I believe this is known in the literature as the problem of finding a strong k-coloring for a k-uniform hypergraph. This should be a good place to start: [PDF].

Improve this answer
$\endgroup$
10
$\begingroup$

It is also at most as hard as $k$-coloring a graph $G=(X,E)$, where $E$ is formed by making each $X_i$ into a clique. Your restriction that all $X_i$ are of size $k$ means that you can cover each edge of $G$ with a clique on $k$ vertices.

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ Indeed. This looks like a transformation of Covering By Cliques in Garey/Johnson. NP-complete for fixed $k \ge 3$, but has a polynomial time algorithm for $k \le 2$ (as Falk mentions). $\endgroup$
    – Daniel Apon
    Commented Aug 20, 2010 at 16:21
  • 2
    $\begingroup$ The construction of $G$ suggested here is precisely the Gaifman graph. $\endgroup$
    – András Salamon
    Commented Aug 20, 2010 at 23:26
  • $\begingroup$ That's right. $G$ is indeed the Gaifman graph. $\endgroup$
    – Serge Gaspers
    Commented Aug 21, 2010 at 10:31
8
$\begingroup$

At least as hard as $k$-colouring an arbitrary graph $G = (V,E)$. For each edge $e = \{u,v\}$ you have a subset $X_e = \{ u, v, x(e,3), x(e,4), \dotsc, x(e,k) \}$; here each $x(e,j)$ is a dummy element that is not present in any other subset. If you can $k$-colour $G$, you can easily find a colouring of the set system (just colour the dummy elements greedily), and vice versa.

Improve this answer
$\endgroup$
8
$\begingroup$

A colouring in which every hyperedge is polychromatic (or rainbow) is also known as a strong colouring.

Note that a strong colouring of a hypergraph is precisely a proper colouring of the Gaifman graph of the hypergraph. (The Gaifman graph (or primal graph or 2-section) of a hypergraph is formed by adding edges between any two vertices that appear together in some hyperedge.)

So if you are looking for a $k$-colouring of an $r$-uniform hypergraph $H$, then you can equivalently look for a $k$-colouring of the Gaifman graph of $H$. The case $r=2$ corresponds to graph colouring, which is polynomial-time for $k=2$ and NP-complete for $k\ge 3$. Obviously $r <2$ is trivial, $k\lt r$ leads to no solutions, and the other cases are all NP-complete.

A useful reference which has most of the above definitions is Vitaly I. Voloshin, Coloring Mixed Hypergraphs: Theory, Algorithms and Applications, Fields Institute Monographs 17, AMS, 2002, ISBN 0-8218-2812-6. This book covers the more general case of weak colourings, with particular focus on combining two types of coloured edges: $C$-edges, which have at least two vertices with a common colour, and $D$-edges, which have at least two vertices of different colours.

Improve this answer
$\endgroup$
2
  • $\begingroup$ What would you recommend as a citation for the NP-hardness of the problem? The above book? $\endgroup$
    – domotorp
    Commented Jun 19, 2016 at 21:12
  • $\begingroup$ @domotorp no, the book focuses on weak colouring. See the answer by Jukka. $\endgroup$
    – András Salamon
    Commented Jun 21, 2016 at 10:22

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.