18
$\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.

$\endgroup$
14
$\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].

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

$\endgroup$
  • 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 Aug 20 '10 at 16:21
  • 2
    $\begingroup$ The construction of $G$ suggested here is precisely the Gaifman graph. $\endgroup$ – András Salamon Aug 20 '10 at 23:26
  • $\begingroup$ That's right. $G$ is indeed the Gaifman graph. $\endgroup$ – Serge Gaspers Aug 21 '10 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.

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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