Parameterized Complexity of [Formula: see text]-Path Packing

Given a graph [Formula: see text], [Formula: see text], and integers k and [Formula: see text], the [Formula: see text] -Path Packing problem asks to find k vertex-disjoint paths of length [Formula: see text] that have endpoints in A and internal points in [Formula: see text]. We study the parameter...

Descripción completa

Detalles Bibliográficos
Autores principales: Belmonte, Rémy, Hanaka, Tesshu, Kanzaki, Masaaki, Kiyomi, Masashi, Kobayashi, Yasuaki, Kobayashi, Yusuke, Lampis, Michael, Ono, Hirotaka, Otachi, Yota
Formato: Online Artículo Texto
Lenguaje:English
Publicado: 2020
Materias:
Article
Acceso en línea:https://www.ncbi.nlm.nih.gov/pmc/articles/PMC7254919/
http://dx.doi.org/10.1007/978-3-030-48966-3_4
Descripción
Sumario:Given a graph [Formula: see text], [Formula: see text], and integers k and [Formula: see text], the [Formula: see text] -Path Packing problem asks to find k vertex-disjoint paths of length [Formula: see text] that have endpoints in A and internal points in [Formula: see text]. We study the parameterized complexity of this problem with parameters |A|, [Formula: see text], k, treewidth, pathwidth, and their combinations. We present sharp complexity contrasts with respect to these parameters. Among other results, we show that the problem is polynomial-time solvable when [Formula: see text], while it is NP-complete for constant [Formula: see text]. We also show that the problem is W[1]-hard parameterized by pathwidth[Formula: see text], while it is fixed-parameter tractable parameterized by treewidth[Formula: see text].

Ejemplares similares