Polynomial-Time Algorithms for Path Cover on Trees and Graphs of Bounded Treewidth
Lists
Only you see this
Abstract
In the Path Cover problem, one asks to cover the vertices of a graph using the smallest possible number of (not necessarily disjoint) paths. While the variant where the paths need to be pairwise vertex-disjoint, which we call Path Partition, is extensively studied, surprisingly little is known about Path Cover. We start filling this gap by designing a linear-time algorithm for Path Cover on trees. Let t be the treewidth of a given graph. We then show that Path Cover can be solved in polynomial time on graphs of bounded treewidth, in XP time \(n^{t^{O(t)}}\), using a dynamic programming scheme. Our algorithm gives an FPT \(2^{O(t\log t)}n\) algorithm for Path Partition as a corollary. These results also apply to the variants where the paths are required to be induced (i.e. chordless) and/or edge-disjoint.
BibTeX
@inproceedings{foucaud2025polynomial,
author = {Florent Foucaud and Atrayee Majumder and Tobias Mömke and Aida Roshany-Tabrizi},
title = {{Polynomial-Time Algorithms for Path Cover on Trees and Graphs of Bounded Treewidth}},
booktitle = {CALDAM},
year = {2025},
doi = {10.1007/978-3-031-83438-7\_13},
}