Path cover using only short paths
Mingyang Gong, Guangting Chen, Zhizhong Chen, Guohui Lin, Riki Uchida · Theoretical Computer Science · 2025
We study a variant of the well-known Path Cover problem where the candidate paths in a solution have orders up to a fixed integer k . In Path Cover, one finds a minimum number of vertex-disjoint paths in an input graph to cover all the vertices; in our variant, not all paths but only those short ones, i.e., containing up to k vertices, can be used as candidates. The problem is NP-hard when k ≥ 3 ; in the literature, there exist quite a number of approximation algorithms, especially for small k 's. We present an improved k 3 -approximation algorithm for k ∈ { 6 , 7 , 8 } , an improved 55 31 -approximation algorithm for k = 5 , and an improved 8 5 -approximation algorithm for k = 4 . The novelty inside these improved algorithms is observing a close connection between an optimal path cover and a certain polynomial-time computed edge set.