Path cover using only short paths

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.

Authors

• Mingyang Gong
• Guangting Chen
• Zhi-Zhong Chen
• Guohui Lin
• Riki Uchida

Keywords

• Path cover
• Path partition
• 2-piece packing
• Approximation algorithm