The complexity of packing edge-disjoint paths

Jan Dreier, Janosch Fuchs, Tim A. Hartmann, Philipp Kuinke, Peter Rossmanith, Bjoern Tauer, Hung Lung Wang

研究成果: 書貢獻/報告類型會議論文篇章

摘要

We introduce and study the complexity of Path Packing. Given a graph G and a list of paths, the task is to embed the paths edge-disjoint in G. This generalizes the well known Hamiltonian-Path problem. Since Hamiltonian Path is efficiently solvable for graphs of small treewidth, we study how this result translates to the much more general Path Packing. On the positive side, we give an FPT-algorithm on trees for the number of paths as parameter. Further, we give an XP-algorithm with the combined parameters maximal degree, number of connected components and number of nodes of degree at least three. Surprisingly the latter is an almost tight result by runtime and parameterization. We show an ETH lower bound almost matching our runtime. Moreover, if two of the three values are constant and one is unbounded the problem becomes NP-hard. Further, we study restrictions to the given list of paths. On the positive side, we present an FPT-algorithm parameterized by the sum of the lengths of the paths. Packing paths of length two is polynomial time solvable, while packing paths of length three is NP-hard. Finally, even the spacial case Exact Path Packing where the paths have to cover every edge in G exactly once is already NP-hard for two paths on 4-regular graphs.

原文英語
主出版物標題14th International Symposium on Parameterized and Exact Computation, IPEC 2019
編輯Bart M. P. Jansen, Jan Arne Telle
發行者Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN(電子)9783959771290
DOIs
出版狀態已發佈 - 2019 十二月
事件14th International Symposium on Parameterized and Exact Computation, IPEC 2019 - Munich, 德国
持續時間: 2019 九月 112019 九月 13

出版系列

名字Leibniz International Proceedings in Informatics, LIPIcs
148
ISSN(列印)1868-8969

會議

會議14th International Symposium on Parameterized and Exact Computation, IPEC 2019
國家/地區德国
城市Munich
期間2019/09/112019/09/13

ASJC Scopus subject areas

  • 軟體

指紋

深入研究「The complexity of packing edge-disjoint paths」主題。共同形成了獨特的指紋。

引用此