TUTCRIS - Tampereen teknillinen yliopisto

TUTCRIS

On the Fine-Grained Complexity of Rainbow Coloring

Tutkimustuotosvertaisarvioitu

Standard

On the Fine-Grained Complexity of Rainbow Coloring. / Kowalik, Lukasz; Lauri, Juho; Socala, Arkadiusz.

24th Annual European Symposium on Algorithms (ESA 2016). toim. / Piotr Sankowski; Christos Zaroliagis. Vuosikerta 57 2016. (Leibniz International Proceedings in Informatics (LIPIcs); Vuosikerta 57).

Tutkimustuotosvertaisarvioitu

Harvard

Kowalik, L, Lauri, J & Socala, A 2016, On the Fine-Grained Complexity of Rainbow Coloring. julkaisussa P Sankowski & C Zaroliagis (toim), 24th Annual European Symposium on Algorithms (ESA 2016). Vuosikerta. 57, Leibniz International Proceedings in Informatics (LIPIcs), Vuosikerta. 57, EUROPEAN SYMPOSIUM ON ALGORITHMS, 1/01/00. https://doi.org/10.4230/LIPIcs.ESA.2016.58

APA

Kowalik, L., Lauri, J., & Socala, A. (2016). On the Fine-Grained Complexity of Rainbow Coloring. teoksessa P. Sankowski, & C. Zaroliagis (Toimittajat), 24th Annual European Symposium on Algorithms (ESA 2016) (Vuosikerta 57). (Leibniz International Proceedings in Informatics (LIPIcs); Vuosikerta 57). https://doi.org/10.4230/LIPIcs.ESA.2016.58

Vancouver

Kowalik L, Lauri J, Socala A. On the Fine-Grained Complexity of Rainbow Coloring. julkaisussa Sankowski P, Zaroliagis C, toimittajat, 24th Annual European Symposium on Algorithms (ESA 2016). Vuosikerta 57. 2016. (Leibniz International Proceedings in Informatics (LIPIcs)). https://doi.org/10.4230/LIPIcs.ESA.2016.58

Author

Kowalik, Lukasz ; Lauri, Juho ; Socala, Arkadiusz. / On the Fine-Grained Complexity of Rainbow Coloring. 24th Annual European Symposium on Algorithms (ESA 2016). Toimittaja / Piotr Sankowski ; Christos Zaroliagis. Vuosikerta 57 2016. (Leibniz International Proceedings in Informatics (LIPIcs)).

Bibtex - Lataa

@inproceedings{759a0eda3a094d6c8bcd871d866c2659,
title = "On the Fine-Grained Complexity of Rainbow Coloring",
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 k >= 2, 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 the 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 Subset 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 k >= 2, extending the result of Ananth et al. [FSTTCS 2011]. We believe that our techniques used for the lower bounds may shed some light on the complexity of the classical Edge Coloring problem, where it is a major open question if a 2^{O(n)}-time algorithm exists.",
keywords = "graph coloring, computational complexity, lower bounds, exponential time hypothesis, FPT algorithms",
author = "Lukasz Kowalik and Juho Lauri and Arkadiusz Socala",
note = "JUFOID=79091",
year = "2016",
doi = "10.4230/LIPIcs.ESA.2016.58",
language = "English",
volume = "57",
series = "Leibniz International Proceedings in Informatics (LIPIcs)",
editor = "Piotr Sankowski and Christos Zaroliagis",
booktitle = "24th Annual European Symposium on Algorithms (ESA 2016)",

}

RIS (suitable for import to EndNote) - Lataa

TY - GEN

T1 - On the Fine-Grained Complexity of Rainbow Coloring

AU - Kowalik, Lukasz

AU - Lauri, Juho

AU - Socala, Arkadiusz

N1 - JUFOID=79091

PY - 2016

Y1 - 2016

N2 - 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 k >= 2, 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 the 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 Subset 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 k >= 2, extending the result of Ananth et al. [FSTTCS 2011]. We believe that our techniques used for the lower bounds may shed some light on the complexity of the classical Edge Coloring problem, where it is a major open question if a 2^{O(n)}-time algorithm exists.

AB - 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 k >= 2, 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 the 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 Subset 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 k >= 2, extending the result of Ananth et al. [FSTTCS 2011]. We believe that our techniques used for the lower bounds may shed some light on the complexity of the classical Edge Coloring problem, where it is a major open question if a 2^{O(n)}-time algorithm exists.

KW - graph coloring

KW - computational complexity

KW - lower bounds

KW - exponential time hypothesis

KW - FPT algorithms

U2 - 10.4230/LIPIcs.ESA.2016.58

DO - 10.4230/LIPIcs.ESA.2016.58

M3 - Conference contribution

VL - 57

T3 - Leibniz International Proceedings in Informatics (LIPIcs)

BT - 24th Annual European Symposium on Algorithms (ESA 2016)

A2 - Sankowski, Piotr

A2 - Zaroliagis, Christos

ER -