Fine-grained complexity of rainbow coloring and its variants
Let \(G\) be a graph and \(c_R : E(G) \rightarrow [k]\) be an edge-coloring of \(G\). A rainbow path between \(u, v \in V (G)\) is a path \(P\) from \(u\) to \(v\) such that for all \(e, e' \in E(P)\), where \(e \neq e'\), we have \(c_R (e) \neq c_R (e')\). In the Rainbow \(k\)-Coloring problem for a given graph \(G\) the objective is to decide if there exists an edge-coloring \(c_R : E(G) \rightarrow [k]\) such that for all \(u, v \in V (G)\) there is a rainbow path between \(u\) and \(v\) in \(G\). Two variants of the above problem are Subset Rainbow \(k\)-Coloring and Steiner Rainbow \(k\)-Coloring, where for a given subset \(S \subseteq V (G) \times V (G)\) respectively \(S' \subseteq V (G)\) the objective is to check if there is \(c_R : E(G) \rightarrow [k]\) such that there is a rainbow path for each \((u, v) \in S\) respectively \(u, v \in S'\). In this paper it is proved that for all \(k \geq 3\), Rainbow \(k\)-Coloring does not admit an algorithm running in time \(2^{o(|E(G)|)}n^{\mathcal{O}(1)}\) unless ETH (Exponential Time Hypothesis) fails. This (partially) solves a conjecture of \textit{Ł. Kowalik} et al. [LIPIcs -- Leibniz Int. Proc. Inform. 57, Article 58, 16 p. (2016; Zbl 1397.68102)]. The author also studies the problem Steiner Rainbow \(k\)-Coloring and proves that for every \(k \geq 3\) the problem does not admit an algorithm running in time \(2^{o(|S|^2)}n^{\mathcal{O}(1)}\) unless ETH fails. She also obtains that for each \(k\geq 3\), Subset Rainbow \(k\)-Coloring and Steiner Rainbow \(k\)-Coloring admit \(2^{\mathcal{O}(|S|)}n^{\mathcal{O}(1)}\)- and \(2^{\mathcal{O}(|S|^{2})}n^{\mathcal{O}(1)}\)-time algorithms, respectively. Three open directions of study conclude the paper.
- An upper bound for the harmonious chromatic number of a graph
- Color-coding
- Hardness and algorithms for rainbow connection
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 1261820 (Why is no real title available?)
- scientific article; zbMATH DE number 1057876 (Why is no real title available?)
- scientific article; zbMATH DE number 1161563 (Why is no real title available?)
- scientific article; zbMATH DE number 6862097 (Why is no real title available?)
- scientific article; zbMATH DE number 2234775 (Why is no real title available?)
- Inapproximability of Rainbow Colouring
- Lower bounds based on the exponential time hypothesis
- On finding rainbow and colorful paths
- On rainbow connection
- On the complexity of k-SAT
- On the fine-grained complexity of rainbow coloring
- On the fine-grained complexity of rainbow coloring
- On the rainbow connectivity of graphs: complexity and FPT algorithms
- Parameterized algorithms
- Parametrized complexity theory.
- Rainbow Colouring of Split and Threshold Graphs
- Rainbow connection in graphs
- Rainbow connectivity: hardness and tractability
- Tight Bounds for Graph Homomorphism and Subgraph Isomorphism
- Tight running time lower bounds for vertex deletion problems
- Upper bounds for harmonious colorings
- Which problems have strongly exponential complexity?
- The algorithmic complexity of colour switching
- On the complexity of \(k\)-rainbow cycle colouring problems
- On finding rainbow and colorful paths
- Inapproximability of Rainbow Colouring
- On the fine-grained complexity of rainbow coloring
- On the fine-grained complexity of rainbow coloring
- Fine-Grained Complexity of Rainbow Coloring and its Variants.
- A survey on rainbow (vertex-)index of graphs
This page was built for publication: Fine-grained complexity of rainbow coloring and its variants
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2051859)
