TUTCRIS - Tampereen teknillinen yliopisto

TUTCRIS

Further hardness results on rainbow and strong rainbow connectivity

Tutkimustuotosvertaisarvioitu

Yksityiskohdat

AlkuperäiskieliEnglanti
Sivut191-200
JulkaisuDiscrete Applied Mathematics
Vuosikerta201
DOI - pysyväislinkit
TilaJulkaistu - 2016
OKM-julkaisutyyppiA1 Alkuperäisartikkeli

Tiivistelmä

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.

Tutkimusalat

Julkaisufoorumi-taso

Tilastokeskuksen tieteenalat