Approximation algorithms for the maximum path cover problem using long paths

The problem studied in this paper is to find a collection of vertex-disjoint paths in a given graph G = ( V, E ) such that each path has length at least k, called a long path, and the total number of edges on these paths is maximized. The problem is NP-hard for any fixed k or when k is part of the input, by a reduction from the Hamiltonian path problem. Berman and Karpinski presented a 7/6-approximation algorithm for k = 1, but for a general k ≥ 2, there is no approximation algorithm directly for the problem. We present the first local search ( 0. 4394 k + O ( 1 ) ) -approximation algorithm for any fixed k ≥ 1, and a 1. 4254-approximation algorithm for k = 2 built on top of a maximum triangle-free path-cycle cover.

Authors

• Mingyang Gong
• Yong Chen
• Zhi-Zhong Chen
• Guohui Lin
• Bing Su
• Lusheng Wang

Keywords

• Path cover
• Path-cycle cover
• Local search
• Recursion
• Approximation algorithm