On the fine-grained complexity of rainbow coloring

DOI10.4230/LIPICS.ESA.2016.58zbMATH Open1397.68102arXiv1602.05608OpenAlexW2889201402MaRDI QIDQ4606330FDOQ4606330

Authors: Łukasz Kowalik, Juho Lauri, Arkadiusz Socała 

Publication date: 2 March 2018

Abstract: The Rainbow k-Coloring problem asks whether the edges of a given graph can be colored in $k$ colors so that every pair of vertices is connected by a rainbow path, i.e., a path with all edges of different colors. Our main result states that for any $kge2$, there is no algorithm for Rainbow k-Coloring running in time $2^{o(n^{3/2})}$, unless ETH fails. Motivated by this negative result we consider two parameterized variants of the problem. In Subset Rainbow k-Coloring problem, introduced by Chakraborty et al. [STACS 2009, J. Comb. Opt. 2009], we are additionally given a set $S$ of pairs of vertices and we ask if there is a coloring in which all the pairs in $S$ are connected by rainbow paths. We show that Subset Rainbow k-Coloring is FPT when parameterized by $|S|$. We also study Maximum Rainbow k-Coloring problem, where we are additionally given an integer $q$ and we ask if there is a coloring in which at least $q$ anti-edges are connected by rainbow paths. We show that the problem is FPT when parameterized by $q$ and has a kernel of size $O(q)$ for every $kge2$ (thus proving that the problem is FPT), extending the result of Ananth et al. [FSTTCS 2011].

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

Recommendations

• On the fine-grained complexity of rainbow coloring
• Fine-grained complexity of rainbow coloring and its variants
• Fine-Grained Complexity of Rainbow Coloring and its Variants.
• Rainbow connectivity: hardness and tractability
• The parameterized complexity of the rainbow subgraph problem

zbMATH Keywords

computational complexitylower boundsgraph coloringexponential time hypothesisFPT algorithms

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Coloring of graphs and hypergraphs (05C15)

Cited In (10)

• The parameterized complexity of the rainbow subgraph problem
• The parameterized complexity of the rainbow subgraph problem
• On finding rainbow and colorful paths
• On the complexity of \(k\)-rainbow cycle colouring problems
• Inapproximability of Rainbow Colouring
• Rainbow vertex coloring bipartite graphs and chordal graphs
• Fine-Grained Complexity of Rainbow Coloring and its Variants.
• The algorithmic complexity of colour switching
• On the fine-grained complexity of rainbow coloring
• Fine-grained complexity of rainbow coloring and its variants

This page was built for publication: On the fine-grained complexity of rainbow coloring

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