On the Complexity of Rainbow Coloring Problems

Eduard Eiben, Robert Ganian, Juho Lauri

Abstract

This paper investigates the computational complexity of rainbow connectivity variants, focusing on the Strong Rainbow Vertex Connection (SRVC) problem. We establish that finding the SRVC number is NP-complete even for graphs with diameter 3. Conversely, we provide linear-time algorithms for various rainbow coloring problems on graphs with restricted structural parameters, such as bounded treewidth or vertex cover number, using Monadic Second Order (MSO) logic and "win-win" algorithmic strategies.

Introduction

Rainbow coloring is a graph-theoretic concept where paths between any two vertices must satisfy a "diversity" constraint: no two edges (or internal vertices) on the path share the same color. This has significant implications for secure and diverse data routing. The paper categorizes these problems into four types based on whether edges or vertices are colored (Rainbow Connection - RC vs. Rainbow Vertex Connection - RVC) and whether the constraint applies to any path or only shortest paths (Standard vs. Strong - SRC/SRVC).

Hardness of Strong Rainbow Vertex Coloring

A major contribution of this work is resolving the complexity of Strong Rainbow Vertex Coloring (SRVC). The authors prove that $k$-SRVC is NP-complete for $k \ge 3$ even on graphs with a diameter of 3. This result is achieved through a polynomial-time reduction from the classic $k$-vertex coloring problem to a specific graph construction, such as a "corona" of a complete graph.

Algorithmic Approaches

While the general problems are NP-hard, the paper identifies structural properties that make them tractable:

  • Monadic Second Order (MSO) Logic: By expressing rainbow coloring requirements as MSO sentences, the authors leverage Courcelle’s Theorem to solve these problems in linear time on graphs with bounded treewidth.
  • Win-Win Strategy: For the "saving $k$ colors" problem, the authors use a dual-path approach. If a graph has high treewidth, it contains structures (like large spanning trees with many leaves) that make rainbow coloring trivial. If the treewidth is low, the MSO-based algorithm is applied.
  • Vertex Cover Number: The paper shows that for graphs with a small vertex cover, RC, RVC, and SRVC can be calculated exactly in linear time, as the rainbow number often correlates with edge separators.

Key Results and Insights

The research demonstrates that the "hardness" of rainbow coloring is tied to how much a graph deviates from being a tree. If a graph is "tree-like" (low treewidth), the problem becomes much easier (linear time). Additionally, the authors established that the SRVC number cannot be efficiently approximated within a factor of $n^{1/2-\epsilon}$ unless P = NP.

Conclusion

The research maps the boundary between tractability and intractability for rainbow coloring. While "flat" graphs with low diameter remain hard to color optimally, "tree-like" graphs or those with small vertex covers allow for efficient solutions. Future work remains in addressing cases where the number of colors $k$ is not fixed and optimizing the large constants associated with MSO-based methods.

Summary updated

Abstract

An edge-colored graph $G$ is said to be rainbow connected if between each pair of vertices there exists a path which uses each color at most once. The rainbow connection number, denoted by $rc(G)$, is the minimum number of colors needed to make $G$ rainbow connected. Along with its variants, which consider vertex colorings and/or so-called strong colorings, the rainbow connection number has been studied from both the algorithmic and graph-theoretic points of view. In this paper we present a range of new results on the computational complexity of computing the four major variants of the rainbow connection number. In particular, we prove that the \textsc{Strong Rainbow Vertex Coloring} problem is $NP$-complete even on graphs of diameter $3$. We show that when the number of colors is fixed, then all of the considered problems can be solved in linear time on graphs of bounded treewidth. Moreover, we provide a linear-time algorithm which decides whether it is possible to obtain a rainbow coloring by saving a fixed number of colors from a trivial upper bound. Finally, we give a linear-time algorithm for computing the exact rainbow connection numbers for three variants of the problem on graphs of bounded vertex cover number.
BibTeX
@article{eiben2018complexity,
  author = {Eduard Eiben and Robert Ganian and Juho Lauri},
  title = {{On the Complexity of Rainbow Coloring Problems}},
  journal = {Discret. Appl. Math.},
  year = {2018},
  doi = {10.1016/j.dam.2016.10.021},
}
Figure