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

2025/11/10 by Florent Foucaud, Atrayee Majumder, Foucaud, Florent +5
Computer Science · #Complexity and Algorithms in Graphs #Advanced Graph Theory Research #Computational Geometry and Mesh Generation

paper · pdf · doi:10.48550/arxiv.2511.07160

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. 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^t^O(t) (where n is the number of vertices and t the treewidth of the input graph) or κ^t^O(t)n if there is an upper-bound κ on the solution size. A similar algorithm gives an FPT 2^{O(tlog t)}n algorithm for PATH PARTITION, which can be improved to (randomized) 2^O(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.

Citations

• Sparsifying, Shrinking and Splicing for Minimum Path Cover in Parameterized Linear Time
• A Single-Exponential Time 2-Approximation Algorithm for Treewidth
• Revisiting path-type covering and partitioning problems
• Solving connectivity problems parameterized by treewidth in single exponential time

Related

• A simple linear-time algorithm for finding path-decompositions of small width
• TREEWIDTH and PATHWIDTH parameterized by vertex cover
• The Complexity of Packing Edge-Disjoint Paths
• Revisiting path-type covering and partitioning problems
• Partitions and Coverings of Trees by Bounded-Degree Subtrees