An improved approximation algorithm for covering vertices by $$4^+$$ 4 + -paths

Mingyang Gong (), Zhi-Zhong Chen (), Guohui Lin () and Lusheng Wang ()
Additional contact information
Mingyang Gong: University of Alberta
Zhi-Zhong Chen: Tokyo Denki University
Guohui Lin: University of Alberta
Lusheng Wang: City University of Hong Kong

Journal of Combinatorial Optimization, 2025, vol. 49, issue 3, No 14, 29 pages

Abstract: Abstract Path cover is one of the well-known NP-hard problems that has received much attention. In this paper, we study a variant of path cover, denoted by $$\hbox {MPC}^{{4}+}_v$$ MPC v 4 + , to cover as many vertices in a given graph $$G = (V, E)$$ G = ( V , E ) as possible by a collection of vertex-disjoint paths each of order four or above. The problem admits an existing $$O(|V|^8)$$ O ( | V | 8 ) -time 2-approximation algorithm by applying several time-consuming local improvement operations (Gong et al.: Proceedings of MFCS 2022, LIPIcs 241, pp 53:1–53:14, 2022). In contrast, our new algorithm uses a completely different method and it is an improved $$O(\min \{|E|^2|V|^2, |V|^5\})$$ O ( min { | E | 2 | V | 2 , | V | 5 } ) -time 1.874-approximation algorithm, which answers the open question in Gong et al. (2022) in the affirmative. An important observation leading to the improvement is that the number of vertices in a maximum matching M of G is relatively large compared to that in an optimal solution of $$\hbox {MPC}^{{4}+}_v$$ MPC v 4 + . Our new algorithm forms a feasible solution of $$\hbox {MPC}^{{4}+}_v$$ MPC v 4 + from a maximum matching M by computing a maximum-weight path-cycle cover in an auxiliary graph to connect as many edges in M as possible.

Keywords: Path cover; Path-cycle cover; Maximum matching; Recursion; Approximation algorithm (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-025-01279-2 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:49:y:2025:i:3:d:10.1007_s10878-025-01279-2

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

DOI: 10.1007/s10878-025-01279-2

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 ().