Polynomial-time algorithms for PATH COVER and PATH PARTITION on trees and graphs of bounded treewidth

Florent Foucaud, Atrayee Majumder, Tobias Mömke +1

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…