Polynomial-Time Algorithms for Path Cover on Trees and Graphs of Bounded Treewidth

Florent Foucaud, Atrayee Majumder, Tobias Mömke, Aida Roshany-Tabrizi

Introduction

Covering the vertices of a graph with the minimum number of paths is a fundamental problem in combinatorial optimization and graph theory. While the Path Partition problem—where paths must be vertex-disjoint—has been a staple of algorithmic research for decades, its counterpart, the Path Cover problem, has remained relatively unexplored. In a Path Cover, paths are permitted to overlap or share vertices, a distinction that significantly alters the problem's combinatorial structure.

Both problems are NP-hard on general graphs, as they generalize the Hamiltonian Path problem. However, for restricted graph classes like trees and graphs of bounded treewidth, efficient solutions are possible. The authors highlight a stark difference in complexity between the two: on a "star" graph with $k$ leaves, a partition requires $k-1$ paths, whereas a cover requires only $\lceil k/2 \rceil$ paths. This paper addresses the gap in literature by providing the first formal algorithmic bounds for Path Cover on these structures, introducing a linear-time algorithm for trees and an XP-time algorithm for graphs of bounded treewidth.

Path Cover on Trees: A Linear-Time Approach

For trees, the authors establish a tight lower bound: the minimum number of paths required to cover all vertices is exactly $\lceil \ell/2 \rceil$, where $\ell$ is the number of leaves in the tree. This stems from the observation that every leaf must serve as an endpoint for at least one path in any valid cover.

To achieve this bound constructively, the authors propose a modified Depth-First Search (DFS) algorithm that runs in $O(n)$ time. The algorithm categorizes paths as either "open" (having one endpoint that is not yet a leaf) or "closed" (both endpoints are leaves). During the backtracking phase of the DFS:

  • Open paths from different subtrees are greedily paired and "closed" at internal nodes.
  • If an internal node cannot pair all incoming open paths, the remaining path stays open to be processed by the node's parent.

This greedy pairing ensures that the total number of paths is minimized to the theoretical leaf-based limit.

Dynamic Programming on Tree Decompositions

Extending the problem to graphs of bounded treewidth $t$ requires more sophisticated machinery. The authors utilize dynamic programming (DP) over a "nice tree decomposition." The primary challenge in Path Cover, as opposed to Path Partition, is the potential for arbitrary overlaps. In a partition, at most $t$ paths can pass through a bag of size $t$, but in a cover, many paths could theoretically share the same set of vertices.

State Representation and Complexity

The DP state characterizes the "type" of each vertex within a bag based on its connectivity to neighbors that are "forgotten" (already processed), "internal" to the bag, or "future" (yet to be seen). To manage overlaps, the algorithm tracks the number of times each specific vertex configuration is utilized.

A vertex configuration representing a path endpoint extending towards unprocessed parts of the graph.
A vertex configuration representing a path passing through a vertex from processed to unprocessed regions.

The resulting algorithm for Path Cover runs in XP time ($n^{t^{O(t)}}$), where the exponent of the vertex count $n$ depends on the treewidth. Interestingly, the authors show that by simplifying this approach to exclude overlaps, they obtain a Fixed-Parameter Tractable (FPT) algorithm for Path Partition with a running time of $2^{O(t \log t)}n$.

Key Insights and Extensions

The research highlights a significant complexity gap between Path Partition and Path Cover on bounded treewidth graphs. While Path Partition is FPT, Path Cover's XP complexity suggests it may be inherently harder due to the unbounded nature of path overlaps within a bag.

Furthermore, the proposed framework is versatile. With minor adjustments to the DP state transitions, the algorithms can be adapted to solve:

  • Induced Path Cover: Where paths must be chordless (induced paths).
  • Edge-Disjoint Path Cover: Where paths can share vertices but not edges.

Conclusion and Future Directions

This work provides a comprehensive algorithmic foundation for the Path Cover problem. By establishing a linear-time solution for trees and an XP-time solution for bounded treewidth graphs, the authors fill a long-standing void in graph theory.

The most prominent open question remains whether Path Cover is actually FPT for treewidth. Future research could also focus on optimizing the $2^{O(t \log t)}$ constant for Path Partition, potentially aiming for a "single-exponential" $2^{O(t)}$ time complexity, similar to recent breakthroughs in the related Cycle Partition problem.

Summary updated

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},
}
Figure