Further hardness results on rainbow and strong rainbow connectivity

DOI10.1016/J.DAM.2015.07.041zbMATH Open1329.05171arXiv1404.3082OpenAlexW1920882336MaRDI QIDQ908308FDOQ908308

Authors: Juho Lauri 

Publication date: 4 February 2016

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Abstract: A path in an edge-colored graph is extit{rainbow} if no two edges of it are colored the same. The graph is said to be extit{rainbow connected} if there is a rainbow path between every pair of vertices. If there is a rainbow shortest path between every pair of vertices, the graph is extit{strong rainbow connected}. We consider the complexity of the problem of deciding if a given edge-colored graph is rainbow or strong rainbow connected. These problems are called extsc{Rainbow connectivity} and extsc{Strong rainbow connectivity}, respectively. We prove both problems remain $NP$hyp{}complete on interval outerplanar graphs and $k$-regular graphs for $kgeq3$. Previously, no graph class was known where the complexity of the two problems would differ. We show that for block graphs, which form a subclass of chordal graphs, extsc{Rainbow connectivity} is $NP$hyp{}complete while extsc{Strong rainbow connectivity} is in $P$. We conclude by considering some tractable special cases, and show for instance that both problems are in $XP$ when parameterized by tree-depth.

Full work available at URL: https://arxiv.org/abs/1404.3082

Recommendations

• Rainbow connectivity: hardness and tractability
• Computing minimum rainbow and strong rainbow colorings of block graphs
• Complexity of rainbow vertex connectivity problems for restricted graph classes
• Hardness and Algorithms for Rainbow Connectivity

zbMATH Keywords

computational complexityrainbow connectivity

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Connectivity (05C40)

Cites Work

• Grad and classes with bounded expansion. I: Decompositions
• Rainbow connection in graphs
• On the rainbow connectivity of graphs: complexity and FPT algorithms
• Hardness and algorithms for rainbow connection
• The rainbow connection of a graph is (at most) reciprocal to its minimum degree
• Title not available (Why is that?)
• Title not available (Why is that?)
• The complexity of determining the rainbow vertex-connection of a graph
• A simplified NP-complete satisfiability problem
• The intersection graphs of subtrees in trees are exactly the chordal graphs
• Note on the complexity of deciding the rainbow (vertex-) connectedness for bipartite graphs
• Title not available (Why is that?)
• The strong rainbow vertex-connection of graphs
• A Characterization of Comparability Graphs and of Interval Graphs
• Rainbow connectivity: hardness and tractability
• New races in parameterized algorithmics
• Pathwidth, Bandwidth, and Completion Problems to Proper Interval Graphs with Small Cliques
• Inapproximability of Rainbow Colouring
• On planar geodetic graphs

Cited In (11)

• On finding rainbow and colorful paths
• Hardness and Algorithms for Rainbow Connectivity
• On the complexity of \(k\)-rainbow cycle colouring problems
• Rainbow vertex coloring bipartite graphs and chordal graphs
• Computing minimum rainbow and strong rainbow colorings of block graphs
• Rainbow connectivity of Moore cages of girth 6
• Algorithms and bounds for very strong rainbow coloring
• Complexity of rainbow vertex connectivity problems for restricted graph classes
• Rainbow connectivity: hardness and tractability
• Algorithm on rainbow connection for maximal outerplanar graphs
• A survey on rainbow (vertex-)index of graphs

This page was built for publication: Further hardness results on rainbow and strong rainbow connectivity

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q908308)