Source-linked AI summary
Hardness and Algorithms for Rainbow Connection
Sourav Chakraborty, Eldar Fischer, Arie Matsliah, Raphael Yuster
TL;DR
The paper studies the computational complexity of rainbow connection and structural conditions that bound it. It proves strong hardness results, gives a polynomial-time coloring algorithm for dense connected graphs, and identifies unresolved bounds and extensions.
Problem
The paper addresses the complexity of computing rainbow connection and verifying rainbow connectivity in arbitrarily edge-colored graphs.
Method
It uses reductions and graph gadgets that encode satisfying assignments as rainbow paths and enforce consistency through edge colors.
Results
Deciding whether rc(G)=2 is NP-Complete, arbitrary edge-colored rainbow connectivity is NP-Complete, and minimum degree at least εn implies rc(G)≤C(ε) with a polynomial-time coloring algorithm.
Takeaways & Limitations
Rainbow connection is computationally hard in general but bounded, and constructively colorable, for connected graphs with sufficiently large minimum degree.
Takeaways & Limitations
The paper leaves the correct dependence of the bounded rainbow-connection constant on ε open, including the possibility that rc(G)≤C/ε for an absolute constant C.
Abstract
from arXiv · showhide
An edge-colored graph $G$ is {\em rainbow connected} if any two vertices are connected by a path whose edges have distinct colors. The {\em rainbow connection} of a connected graph $G$, denoted $rc(G)$, is the smallest number of colors that are needed in order to make $G$ rainbow connected. In the first result of this paper we prove that computing $rc(G)$ is NP-Hard solving an open problem from \cite{Ca-Yu}. In fact, we prove that it is already NP-Complete to decide if $rc(G)=2$, and also that it is NP-Complete to decide whether a given edge-colored (with an unbounded number of colors) graph is rainbow connected. On the positive side, we prove that for every $ε>0$, a connected graph with minimum degree at least $εn$ has {\em bounded} rainbow connection, where the bound depends only on $ε$, and a corresponding coloring can be constructed in polynomial time. Additional non-trivial upper bounds, as well as open problems and conjectures are also presented.
1 Introduction
The paper establishes computational hardness for rainbow connection while proving bounded rainbow connection under strong minimum-degree conditions and presenting algorithmic constructions.
- Hardness results: Deciding whether rc(G)=2 is NP-Complete, implying that computing rc(G) is NP-Hard.
- Hardness results: Checking whether an arbitrary given edge-coloring makes a graph rainbow connected is also NP-Complete.
- Positive algorithmic results: For every ε>0, connected n-vertex graphs with minimum degree at least εn have rainbow connection at most a constant C(ε).A polynomial-time algorithm constructs a corresponding coloring for fixed ε.
- Methods and organization: The paper’s positive proof uses a modified degree-form Szemerédi Regularity Lemma, with derandomization based largely on conditional expectation.
- Positive algorithmic results: Graphs of diameter 2 with minimum degree at least 8 log n satisfy rc(G)≤3.The coloring can be obtained with high probability by uniformly random 3-edge-coloring or by a deterministic polynomial-time algorithm.
- Positive algorithmic results: The bound rc(G)≤3 immediately applies to graphs with minimum degree at least n/2.
2 Hardness results
The paper establishes several NP-completeness results for rainbow connection through polynomial reductions, including hardness for deciding rc(G)=2 and for verifying arbitrary edge colorings. The reductions encode satisfiability and constrained rainbow paths using auxiliary vertices, gadgets, and color assignments.
- Polynomial equivalences: 2-rainbow-colorability and subset rainbow connection with prescribed vertex pairs are polynomially equivalent.The reduction transforms a graph and pair set into a graph whose 2-rainbow connectivity captures rainbow connectivity for exactly those pairs.
- Polynomial equivalences: Partial 2-edge-coloring extension is polynomially reducible to subset rainbow connection with two colors.The construction adds 3 + |Ê_1| + |Ê_2| vertices and enforces the original partial coloring through selected pair constraints and edge colors.
- Hardness reductions: 3-SAT reduces to extending a partial 2-edge-coloring, with satisfiability equivalent to the existence of a rainbow-connected completion.The graph Gφ and partial coloring leave selected edges uncolored; their valid 2-rainbow colorings correspond to satisfying assignments.
- Hardness results: Deciding whether rc(G)=2 is NP-Complete, and computing rc(G) is therefore NP-Hard.The proof combines the reductions establishing polynomial equivalence with the NP-hardness of the partial-coloring extension problem.
- Hardness reductions: A rainbow path between two designated vertices is NP-complete to decide in an arbitrarily edge-colored graph.The reduction constructs Gφ with layered clause vertices, literal gadgets, and colors that prevent paths from selecting contradictory literals.
- Hardness reductions: Opposite literals of the same variable receive paths sharing a color, so a rainbow s-to-t path yields a consistent satisfying assignment.The construction ensures every s-to-t path meets each clause layer, while shared colors exclude simultaneous selection of opposite literals.
3 Upper bounds and algorithms
The section develops a modified Regularity Lemma and uses it with probabilistic coloring to obtain bounded rainbow connection for dense graphs.
- 3.2 A modified degree form version of the Regularity Lemma: The Regularity Lemma approximates a graph using a constant-size partition whose large cluster pairs behave like pseudorandom bipartite graphs.The number of partition classes depends on the regularity parameters rather than directly on the graph size.
- 3.2 A modified degree form version of the Regularity Lemma: A modified degree-form Regularity Lemma partitions dense graphs into structured classes while preserving minimum-degree-related neighborhood properties.The partition has an exceptional class, independent classes, regular inter-class pairs, and a guaranteed neighboring class with many retained neighbors.
- 3.4 Proof of Lemma 3.6: Eight colors are split into four a-colors and four b-colors, requiring vertex pairs within each partition class to be rainbow connected in both systems.This central lemma supplies the local coloring property used to construct a globally rainbow-connected coloring.
- 3. Upper bounds and algorithms: The resulting coloring makes the entire graph rainbow connected and uses at most |E_T| + 8 ≤ C colors, where C depends only on ǫ.Thus connected n-vertex graphs with minimum degree at least ǫn have bounded rainbow connection, with a polynomial-time coloring algorithm.
- 3.4 Proof of Lemma 3.6: Each partition class contains more than 85 log n edge-disjoint paths of length at most four between every vertex pair, and the classes are computable in polynomial time for fixed ǫ.These many short paths support the subsequent random-coloring argument.
- 3.4 Proof of Lemma 3.6: Uniform independent coloring makes a fixed short path rainbow with probability at least 8^-4, yielding positive probability that all required pairs satisfy both rainbow-connectivity conditions.The failure probability for a fixed pair is bounded by 2(1−8^-4)^85 log n < n^-2.
4 Concluding remarks and open problems
The paper identifies unresolved questions about sharper bounds, fixed-k complexity, rainbow diameter, and efficient coloring when rc(G)=2.
- Bounded rainbow connection: The bound for graphs with minimum degree at least ǫn is huge because it follows from the Regularity Lemma.The authors ask for the correct bound and note the possibility that rc(G) ≤ C/ǫ for an absolute constant C.
- Complexity for fixed k: Deciding whether rc(G) ≤ k is not proved NP-Complete for every fixed k, although subdivision gives the result for every even k.The reduction transforms each edge into k/2 edges and relates rc(G′)=k to rc(G)=2.
- Complexity for fixed k: It is conjectured that distinguishing 2-rainbow-colorable graphs from graphs that are not k-rainbow-colorable is NP-Hard for every k.
- Rainbow diameter: Rainbow diameter satisfies rd(G) ≥ rc(G) but is not monotone under edge addition, unlike rainbow connection.The authors conjecture that minimum degree at least ǫn also implies bounded rainbow diameter.
- Efficient coloring: For graphs known to have rc(G)=2, an open problem asks whether a polynomial-time coloring using o(n) colors exists.The section contrasts this with the usual coloring problem, where a polynomial-time 3-coloring algorithm can use ˜O(n3/14) colors.