{"ID":2844001,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2511.07160","arxiv_id":"2511.07160","title":"Polynomial-time algorithms for PATH COVER and PATH PARTITION on trees and graphs of bounded treewidth","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(t\\log t)}n$ algorithm for PATH PARTITION, which can be improved to (randomized) $2^{O(t)}n$ using the Cut\\\u0026Count technique. These results also apply to the variants where the paths are required to be induced (i.e. chordless) and/or edge-disjoint.","short_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 star...","url_abs":"https://arxiv.org/abs/2511.07160","url_pdf":"https://arxiv.org/pdf/2511.07160v1","authors":"[\"Florent Foucaud\",\"Atrayee Majumder\",\"Tobias Mömke\",\"Aida Roshany-Tabrizi\"]","published":"2025-11-10T14:50:22Z","proceeding":"cs.DS","tasks":"[\"cs.DS\",\"cs.DM\"]","methods":"[]","has_code":false}