Polynomial-time algorithms for Path Cover on trees and graphs of bounded treewidth

Overview & Synopsis

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.