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
_version_ 1783539635869188096
author Belmonte, Rémy
Hanaka, Tesshu
Kanzaki, Masaaki
Kiyomi, Masashi
Kobayashi, Yasuaki
Kobayashi, Yusuke
Lampis, Michael
Ono, Hirotaka
Otachi, Yota
author_facet Belmonte, Rémy
Hanaka, Tesshu
Kanzaki, Masaaki
Kiyomi, Masashi
Kobayashi, Yasuaki
Kobayashi, Yusuke
Lampis, Michael
Ono, Hirotaka
Otachi, Yota
author_sort Belmonte, Rémy
collection PubMed
description 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].
format Online
Article
Text
id pubmed-7254919
institution National Center for Biotechnology Information
language English
publishDate 2020
record_format MEDLINE/PubMed
spelling pubmed-72549192020-05-28 Parameterized Complexity of [Formula: see text]-Path Packing Belmonte, Rémy Hanaka, Tesshu Kanzaki, Masaaki Kiyomi, Masashi Kobayashi, Yasuaki Kobayashi, Yusuke Lampis, Michael Ono, Hirotaka Otachi, Yota Combinatorial Algorithms Article 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]. 2020-04-30 /pmc/articles/PMC7254919/ http://dx.doi.org/10.1007/978-3-030-48966-3_4 Text en © Springer Nature Switzerland AG 2020 This article is made available via the PMC Open Access Subset for unrestricted research re-use and secondary analysis in any form or by any means with acknowledgement of the original source. These permissions are granted for the duration of the World Health Organization (WHO) declaration of COVID-19 as a global pandemic.
spellingShingle Article
Belmonte, Rémy
Hanaka, Tesshu
Kanzaki, Masaaki
Kiyomi, Masashi
Kobayashi, Yasuaki
Kobayashi, Yusuke
Lampis, Michael
Ono, Hirotaka
Otachi, Yota
Parameterized Complexity of [Formula: see text]-Path Packing
title Parameterized Complexity of [Formula: see text]-Path Packing
title_full Parameterized Complexity of [Formula: see text]-Path Packing
title_fullStr Parameterized Complexity of [Formula: see text]-Path Packing
title_full_unstemmed Parameterized Complexity of [Formula: see text]-Path Packing
title_short Parameterized Complexity of [Formula: see text]-Path Packing
title_sort parameterized complexity of [formula: see text]-path packing
topic Article
url https://www.ncbi.nlm.nih.gov/pmc/articles/PMC7254919/
http://dx.doi.org/10.1007/978-3-030-48966-3_4
work_keys_str_mv AT belmonteremy parameterizedcomplexityofformulaseetextpathpacking
AT hanakatesshu parameterizedcomplexityofformulaseetextpathpacking
AT kanzakimasaaki parameterizedcomplexityofformulaseetextpathpacking
AT kiyomimasashi parameterizedcomplexityofformulaseetextpathpacking
AT kobayashiyasuaki parameterizedcomplexityofformulaseetextpathpacking
AT kobayashiyusuke parameterizedcomplexityofformulaseetextpathpacking
AT lampismichael parameterizedcomplexityofformulaseetextpathpacking
AT onohirotaka parameterizedcomplexityofformulaseetextpathpacking
AT otachiyota parameterizedcomplexityofformulaseetextpathpacking

Ejemplares similares