TUTCRIS - Tampereen teknillinen yliopisto

TUTCRIS

Complexity of Rainbow Vertex Connectivity Problems for Restricted Graph Classes

Tutkimustuotosvertaisarvioitu

Yksityiskohdat

AlkuperäiskieliEnglanti
Sivut132-146
Sivumäärä14
JulkaisuDiscrete Applied Mathematics
Vuosikerta219
Varhainen verkossa julkaisun päivämäärä15 joulukuuta 2016
DOI - pysyväislinkit
TilaJulkaistu - 11 maaliskuuta 2017
OKM-julkaisutyyppiA1 Alkuperäisartikkeli

Tiivistelmä

A path in a vertex-colored graph G is vertex rainbow if all of its internal vertices have a distinct color. The graph G is said to be rainbow vertex connected if there is a vertex rainbow path between every pair of its vertices. Similarly, the graph G is strongly rainbow vertex connected if there is a shortest path which is vertex rainbow between every pair of its vertices. We consider the complexity of deciding if a given vertex-colored graph is rainbow or strongly rainbow vertex connected. We call these problems Rainbow Vertex Connectivity and Strong Rainbow Vertex Connectivity, respectively. We prove both problems remain NP-complete on very restricted graph classes including bipartite planar graphs of maximum degree 3, interval graphs, and kk-regular graphs for k≥3k≥3. We settle precisely the complexity of both problems from the viewpoint of two width parameters: pathwidth and tree-depth. More precisely, we show both problems remain NP-complete for bounded pathwidth graphs, while being fixed-parameter tractable parameterized by tree-depth. Moreover, we show both problems are solvable in polynomial time for block graphs, while Strong Rainbow Vertex Connectivity is tractable for cactus graphs and split graphs.

Julkaisufoorumi-taso

Tilastokeskuksen tieteenalat