An improved approximation algorithm for the minimum 3-path partition problem

Yong Chen (), Randy Goebel (), Guohui Lin (), Bing Su (), Yao Xu () and An Zhang ()
Additional contact information
Yong Chen: Hangzhou Dianzi University
Randy Goebel: University of Alberta
Guohui Lin: University of Alberta
Bing Su: Xi’an Technological University
Yao Xu: University of Alberta
An Zhang: Hangzhou Dianzi University

Journal of Combinatorial Optimization, 2019, vol. 38, issue 1, No 8, 150-164

Abstract: Abstract Given a graph $$G = (V, E)$$ G = ( V , E ) , we seek for a collection of vertex disjoint paths each of order at most 3 that together cover all the vertices of V. The problem is called 3-path partition, and it has close relationships to the well-known path cover problem and the set cover problem. The general k-path partition problem for a constant $$k \ge 3$$ k ≥ 3 is NP-hard, and it admits a trivial k-approximation. When $$k = 3$$ k = 3 , the previous best approximation ratio is 1.5 due to Monnot and Toulouse (Oper Res Lett 35:677–684, 2007), based on two maximum matchings. In this paper we first show how to compute in polynomial time a 3-path partition with the least 1-paths, and then apply a greedy approach to merge three 2-paths into two 3-paths whenever possible. Through an amortized analysis, we prove that the proposed algorithm is a 13 / 9-approximation. We also show that the performance ratio 13 / 9 is tight for our algorithm.

Keywords: k-Path partition; Path cover; k-Set cover; Approximation algorithm; Amortized analysis (search for similar items in EconPapers)
Date: 2019
References: View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://link.springer.com/10.1007/s10878-018-00372-z Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:38:y:2019:i:1:d:10.1007_s10878-018-00372-z

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-018-00372-z

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().