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

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. We show that PATH COVER can be solved in polynomial time on graphs of bounded treewidth using a dynamic programming scheme. It runs in XP time n^tO(t) (where n is the number of vertices and t the treewidth of the input graph) or κ^tO(t)n if there is an upper-bound $κ$ on the solution size. A similar algorithm gives an FPT 2O(tlog t)n algorithm for PATH PARTITION, which can be improved to (randomized) 2O(t)n using the Cut&Count technique. These results also apply to the variants where the paths are required to be induced (i.e. chordless) and/or edge-disjoint.