TUTCRIS - Tampereen teknillinen yliopisto

TUTCRIS

Further hardness results on rainbow and strong rainbow connectivity

Tutkimustuotosvertaisarvioitu

Standard

Further hardness results on rainbow and strong rainbow connectivity. / Lauri, Juho.

julkaisussa: Discrete Applied Mathematics, Vuosikerta 201, 2016, s. 191-200.

Tutkimustuotosvertaisarvioitu

Harvard

Lauri, J 2016, 'Further hardness results on rainbow and strong rainbow connectivity', Discrete Applied Mathematics, Vuosikerta. 201, Sivut 191-200. https://doi.org/10.1016/j.dam.2015.07.041

APA

Vancouver

Author

Lauri, Juho. / Further hardness results on rainbow and strong rainbow connectivity. Julkaisussa: Discrete Applied Mathematics. 2016 ; Vuosikerta 201. Sivut 191-200.

Bibtex - Lataa

@article{28841fe340c3448e8a3bf9c7797d0568,
title = "Further hardness results on rainbow and strong rainbow connectivity",
abstract = "A path in an edge-colored graph is rainbow if no two edges of it are colored the same. The graph is said to be 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 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 Rainbow connectivity and Strong rainbow connectivity, respectively. We prove both problems remain NP-complete on interval outerplanar graphs and k-regular graphs for k≥3. 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, Rainbow connectivity is NP-complete while 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.",
keywords = "Computational complexity, Rainbow connectivity",
author = "Juho Lauri",
year = "2016",
doi = "10.1016/j.dam.2015.07.041",
language = "English",
volume = "201",
pages = "191--200",
journal = "Discrete Applied Mathematics",
issn = "0166-218X",
publisher = "Elsevier",

}

RIS (suitable for import to EndNote) - Lataa

TY - JOUR

T1 - Further hardness results on rainbow and strong rainbow connectivity

AU - Lauri, Juho

PY - 2016

Y1 - 2016

N2 - A path in an edge-colored graph is rainbow if no two edges of it are colored the same. The graph is said to be 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 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 Rainbow connectivity and Strong rainbow connectivity, respectively. We prove both problems remain NP-complete on interval outerplanar graphs and k-regular graphs for k≥3. 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, Rainbow connectivity is NP-complete while 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.

AB - A path in an edge-colored graph is rainbow if no two edges of it are colored the same. The graph is said to be 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 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 Rainbow connectivity and Strong rainbow connectivity, respectively. We prove both problems remain NP-complete on interval outerplanar graphs and k-regular graphs for k≥3. 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, Rainbow connectivity is NP-complete while 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.

KW - Computational complexity

KW - Rainbow connectivity

U2 - 10.1016/j.dam.2015.07.041

DO - 10.1016/j.dam.2015.07.041

M3 - Article

VL - 201

SP - 191

EP - 200

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

SN - 0166-218X

ER -