Approximately Partitioning Vertices into Short Paths

arXiv:2602.03991v1 Announce Type: new
Abstract: Given a fixed positive integer $k$ and a simple undirected graph $G = (V, E)$, the {em $k^-$-path partition} problem, denoted by $k$PP for short, aims to find a minimum collection $cal{P}$ of vertex-disjoint paths in $G$ such that each path in $cal{P}$ has at most $k$ vertices and each vertex of $G$ appears in one path in $cal{P}$. In this paper, we present a $frac {k+4}5$-approximation algorithm for $k$PP when $kin{9,10}$ and an improved $(frac{sqrt{11}-2}7 k + frac {9-sqrt{11}}7)$-approximation algorithm when $k ge 11$. Our algorithms achieve the current best approximation ratios for $k in { 9, 10, ldots, 18 }$.
Our algorithms start with a maximum triangle-free path-cycle cover $cal{F}$, which may not be feasible because of the existence of cycles or paths with more than $k$ vertices. We connect as many cycles in $cal{F}$ with $4$ or $5$ vertices as possible by computing another maximum-weight path-cycle cover in a suitably constructed graph so that $cal{F}$ can be transformed into a $k^-$-path partition of $G$ without losing too many edges.
Keywords: $k^-$-path partition; Triangle-free path-cycle cover; $[f, g]$-factor; Approximation algorithm