Approximately covering vertices by order-5 or longer paths

Mingyang Gong; Zhi-Zhong Chen; Guohui Lin; Lusheng Wang

doi:10.1016/j.jcss.2025.103704

Approximately covering vertices by order-5 or longer paths

Mingyang Gong, Zhi-Zhong Chen^*, Guohui Lin^*, Lusheng Wang

^*Corresponding author for this work

Department of Computer Science

Research output: Journal Publications and Reviews › RGC 21 - Publication in refereed journal › peer-review

3 Downloads (CityUHK Scholars)

Abstract

This paper studies MPC_v⁵⁺, which is to cover as many vertices as possible in a given graph G=(V,E) by vertex-disjoint 5⁺-paths (i.e., paths each with at least five vertices). MPC_v⁵⁺ is NP-hard and admits an existing local-search-based approximation algorithm which achieves a ratio of [Formula presented] and runs in O(|V|⁶) time. In this paper, we present a new approximation algorithm for MPC_v⁵⁺ which achieves a ratio of 2.511 and runs in O(|V|^2.5|E|²) time. Unlike the previous algorithm, the new algorithm is based on maximum matching, maximum path-cycle cover, and recursion. © 2025 The Author(s)

Original language	English
Article number	103704
Journal	Journal of Computer and System Sciences
Volume	156
Online published	3 Sept 2025
DOIs	https://doi.org/10.1016/j.jcss.2025.103704
Publication status	Published - Mar 2026

Funding

This research is supported by the Ministry of Science and Technology of the People's Republic of China ( G2023016016L ), the NSERC Canada, the Grant-in-Aid for Scientific Research of the Ministry of Education, Science, Sports and Culture of Japan (Grant No. 18K11183 ), the National Natural Science Foundation of China (Grant No. 61972329 ), and the GRF grants for Hong Kong Special Administrative Region, China ( CityU 11218821 , CityU 11218423 ).

Research Keywords

Approximation algorithm
Long path
Maximum matching
Path cover
Recursion

Publisher's Copyright Statement

This full text is made available under CC-BY 4.0. https://creativecommons.org/licenses/by/4.0/

RGC Funding Information

RGC-funded

Access Output

10.1016/j.jcss.2025.103704

350592510.pdfFinal Published version, 1.72 MBLicence: CC BY

Other Access Options

Check CityUHK Library

Permanent Link

Right click to copy link

Cite this

@article{e6eb828fb9284f959fa97bf2664ebc02,

title = "Approximately covering vertices by order-5 or longer paths",

abstract = "This paper studies MPCv5+, which is to cover as many vertices as possible in a given graph G=(V,E) by vertex-disjoint 5+-paths (i.e., paths each with at least five vertices). MPCv5+ is NP-hard and admits an existing local-search-based approximation algorithm which achieves a ratio of [Formula presented] and runs in O(|V|6) time. In this paper, we present a new approximation algorithm for MPCv5+ which achieves a ratio of 2.511 and runs in O(|V|2.5|E|2) time. Unlike the previous algorithm, the new algorithm is based on maximum matching, maximum path-cycle cover, and recursion. {\textcopyright} 2025 The Author(s)",

keywords = "Approximation algorithm, Long path, Maximum matching, Path cover, Recursion",

author = "Mingyang Gong and Zhi-Zhong Chen and Guohui Lin and Lusheng Wang",

year = "2026",

month = mar,

doi = "10.1016/j.jcss.2025.103704",

language = "English",

volume = "156",

journal = "Journal of Computer and System Sciences",

issn = "0022-0000",

publisher = "Academic Press Inc.",

}

TY - JOUR

T1 - Approximately covering vertices by order-5 or longer paths

AU - Gong, Mingyang

AU - Chen, Zhi-Zhong

AU - Lin, Guohui

AU - Wang, Lusheng

PY - 2026/3

Y1 - 2026/3

N2 - This paper studies MPCv5+, which is to cover as many vertices as possible in a given graph G=(V,E) by vertex-disjoint 5+-paths (i.e., paths each with at least five vertices). MPCv5+ is NP-hard and admits an existing local-search-based approximation algorithm which achieves a ratio of [Formula presented] and runs in O(|V|6) time. In this paper, we present a new approximation algorithm for MPCv5+ which achieves a ratio of 2.511 and runs in O(|V|2.5|E|2) time. Unlike the previous algorithm, the new algorithm is based on maximum matching, maximum path-cycle cover, and recursion. © 2025 The Author(s)

AB - This paper studies MPCv5+, which is to cover as many vertices as possible in a given graph G=(V,E) by vertex-disjoint 5+-paths (i.e., paths each with at least five vertices). MPCv5+ is NP-hard and admits an existing local-search-based approximation algorithm which achieves a ratio of [Formula presented] and runs in O(|V|6) time. In this paper, we present a new approximation algorithm for MPCv5+ which achieves a ratio of 2.511 and runs in O(|V|2.5|E|2) time. Unlike the previous algorithm, the new algorithm is based on maximum matching, maximum path-cycle cover, and recursion. © 2025 The Author(s)

KW - Approximation algorithm

KW - Long path

KW - Maximum matching

KW - Path cover

KW - Recursion

UR - http://www.scopus.com/inward/record.url?scp=105015044549&partnerID=8YFLogxK

UR - https://www.scopus.com/record/pubmetrics.uri?eid=2-s2.0-105015044549&origin=recordpage

U2 - 10.1016/j.jcss.2025.103704

DO - 10.1016/j.jcss.2025.103704

M3 - RGC 21 - Publication in refereed journal

SN - 0022-0000

VL - 156

JO - Journal of Computer and System Sciences

JF - Journal of Computer and System Sciences

M1 - 103704

ER -

Approximately covering vertices by order-5 or longer paths

Abstract

Funding

Research Keywords

Publisher's Copyright Statement

RGC Funding Information

Access Output

Other Access Options

Permanent Link

Other Files and Links

Fingerprint

GRF: Algorithms for Proteoform Detection and Multiplexed Protein Sequencing

GRF: Algorithms for Identification and Quantification of Proteoforms Using Multiplexed Tandem Mass Spectra and De Novo Sequencing of Mixture Spectra

Cite this

Approximately covering vertices by order-5 or longer paths

Abstract

Funding

Research Keywords

Publisher's Copyright Statement

RGC Funding Information

Access Output

Other Access Options

Permanent Link

Other Files and Links

Fingerprint

Projects

GRF: Algorithms for Proteoform Detection and Multiplexed Protein Sequencing

GRF: Algorithms for Identification and Quantification of Proteoforms Using Multiplexed Tandem Mass Spectra and De Novo Sequencing of Mixture Spectra

Cite this