Approximately Covering Vertices by Order-5 or Longer Paths

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

doi:10.1007/978-981-96-1090-7_41

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: Chapters, Conference Papers, Creative and Literary Works › RGC 32 - Refereed conference paper (with host publication) › peer-review

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 ¹⁹⁄₇ ≈ 2.714 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(max{|E|²|V|^2.5,|E||V|⁴}) time. Unlike the previous algorithm, the new algorithm is based on maximum matching, maximum path-cycle cover, and recursion. © The Author(s), under exclusive license to Springer Nature Singapore Pte Ltd. 2025.

Original language	English
Title of host publication	Computing and Combinatorics
Subtitle of host publication	30th International Conference, COCOON 2024, Shanghai, China, August 23–25, 2024, Proceedings, Part I
Editors	Yong Chen, Xiaofeng Gao, Xiaoming Sun, An Zhang
Place of Publication	Singapore
Publisher	Springer
Pages	505-517
ISBN (Electronic)	978-981-96-1090-7
ISBN (Print)	9789819610891
DOIs	https://doi.org/10.1007/978-981-96-1090-7_41
Publication status	Published - 2025
Event	30^th International Computing and Combinatorics Conference (COCOON 2024) - Jin Jiang Hotel Shanghai, Shanghai, China Duration: 23 Aug 2024 → 25 Aug 2024 https://anl.sjtu.edu.cn/cocoon2024/

Publication series

Name	Lecture Notes in Computer Science
Volume	15161
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	30^th International Computing and Combinatorics Conference (COCOON 2024)
Country/Territory	China
City	Shanghai
Period	23/08/24 → 25/08/24
Internet address	https://anl.sjtu.edu.cn/cocoon2024/

Funding

This research is supported by 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 Science Foundation of China (Grant No. 61972329), the GRF grants for Hong Kong Special Administrative Region, China (CityU 11206120, CityU 11210119, CityU 11218821), a grant from City University of Hong Kong (CityU 11214522), and the Ministry of Science and Technology of China (G2022040004L, G2023016016L).

Research Keywords

approximation algorithm
long path
maximum matching
Path cover
recursion

Access Output

10.1007/978-981-96-1090-7_41

Other Access Options

Check CityUHK Library

Permanent Link

Right click to copy link

Cite this

Gong, M., Chen, Z.-Z., Lin, G., & Wang, L. (2025). Approximately Covering Vertices by Order-5 or Longer Paths. In Y. Chen, X. Gao, X. Sun, & A. Zhang (Eds.), Computing and Combinatorics: 30th International Conference, COCOON 2024, Shanghai, China, August 23–25, 2024, Proceedings, Part I (pp. 505-517). (Lecture Notes in Computer Science; Vol. 15161). Springer . https://doi.org/10.1007/978-981-96-1090-7_41

Gong, Mingyang ; Chen, Zhi-Zhong ; Lin, Guohui et al. / Approximately Covering Vertices by Order-5 or Longer Paths. Computing and Combinatorics: 30th International Conference, COCOON 2024, Shanghai, China, August 23–25, 2024, Proceedings, Part I. editor / Yong Chen ; Xiaofeng Gao ; Xiaoming Sun ; An Zhang. Singapore : Springer , 2025. pp. 505-517 (Lecture Notes in Computer Science).

@inproceedings{cc0f5b8fb5534d9b9dbd3faba7f40832,

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 19⁄7 ≈ 2.714 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(max{|E|2|V|2.5,|E||V|4}) time. Unlike the previous algorithm, the new algorithm is based on maximum matching, maximum path-cycle cover, and recursion. {\textcopyright} The Author(s), under exclusive license to Springer Nature Singapore Pte Ltd. 2025.",

keywords = "approximation algorithm, long path, maximum matching, Path cover, recursion",

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

year = "2025",

doi = "10.1007/978-981-96-1090-7_41",

language = "English",

isbn = "9789819610891",

series = "Lecture Notes in Computer Science",

publisher = "Springer ",

pages = "505--517",

editor = "Yong Chen and Xiaofeng Gao and Xiaoming Sun and An Zhang",

booktitle = "Computing and Combinatorics",

note = "30<sup>th</sup> International Computing and Combinatorics Conference (COCOON 2024) ; Conference date: 23-08-2024 Through 25-08-2024",

url = "https://anl.sjtu.edu.cn/cocoon2024/",

}

Gong, M, Chen, Z-Z, Lin, G & Wang, L 2025, Approximately Covering Vertices by Order-5 or Longer Paths. in Y Chen, X Gao, X Sun & A Zhang (eds), Computing and Combinatorics: 30th International Conference, COCOON 2024, Shanghai, China, August 23–25, 2024, Proceedings, Part I. Lecture Notes in Computer Science, vol. 15161, Springer , Singapore, pp. 505-517, 30^th International Computing and Combinatorics Conference (COCOON 2024), Shanghai, China, 23/08/24. https://doi.org/10.1007/978-981-96-1090-7_41

Approximately Covering Vertices by Order-5 or Longer Paths. / Gong, Mingyang; Chen, Zhi-Zhong; Lin, Guohui et al.
Computing and Combinatorics: 30th International Conference, COCOON 2024, Shanghai, China, August 23–25, 2024, Proceedings, Part I. ed. / Yong Chen; Xiaofeng Gao; Xiaoming Sun; An Zhang. Singapore: Springer , 2025. p. 505-517 (Lecture Notes in Computer Science; Vol. 15161).

Research output: Chapters, Conference Papers, Creative and Literary Works › RGC 32 - Refereed conference paper (with host publication) › peer-review

TY - GEN

T1 - Approximately Covering Vertices by Order-5 or Longer Paths

AU - Gong, Mingyang

AU - Chen, Zhi-Zhong

AU - Lin, Guohui

AU - Wang, Lusheng

PY - 2025

Y1 - 2025

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 19⁄7 ≈ 2.714 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(max{|E|2|V|2.5,|E||V|4}) time. Unlike the previous algorithm, the new algorithm is based on maximum matching, maximum path-cycle cover, and recursion. © The Author(s), under exclusive license to Springer Nature Singapore Pte Ltd. 2025.

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 19⁄7 ≈ 2.714 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(max{|E|2|V|2.5,|E||V|4}) time. Unlike the previous algorithm, the new algorithm is based on maximum matching, maximum path-cycle cover, and recursion. © The Author(s), under exclusive license to Springer Nature Singapore Pte Ltd. 2025.

KW - approximation algorithm

KW - long path

KW - maximum matching

KW - Path cover

KW - recursion

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

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

U2 - 10.1007/978-981-96-1090-7_41

DO - 10.1007/978-981-96-1090-7_41

M3 - RGC 32 - Refereed conference paper (with host publication)

SN - 9789819610891

T3 - Lecture Notes in Computer Science

SP - 505

EP - 517

BT - Computing and Combinatorics

A2 - Chen, Yong

A2 - Gao, Xiaofeng

A2 - Sun, Xiaoming

A2 - Zhang, An

PB - Springer

CY - Singapore

T2 - 30<sup>th</sup> International Computing and Combinatorics Conference (COCOON 2024)

Y2 - 23 August 2024 through 25 August 2024

ER -

Gong M, Chen ZZ, Lin G, Wang L. Approximately Covering Vertices by Order-5 or Longer Paths. In Chen Y, Gao X, Sun X, Zhang A, editors, Computing and Combinatorics: 30th International Conference, COCOON 2024, Shanghai, China, August 23–25, 2024, Proceedings, Part I. Singapore: Springer . 2025. p. 505-517. (Lecture Notes in Computer Science). Epub 2025 Mar 5. doi: 10.1007/978-981-96-1090-7_41

Approximately Covering Vertices by Order-5 or Longer Paths

Abstract

Publication series

Conference

Funding

Research Keywords

Access Output

Other Access Options

Permanent Link

Other Files and Links

Fingerprint

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

GRF: Algorithms for Searching MS Spectra against Protein Databases and Protein Sequencing Using Combined Top-down and Bottom-up Approach for Monoclonal Antibodies

GRF: Efficient Algorithms for Identification of Modified Proteoforms Using Top-down Mass Spectra

Cite this

Approximately Covering Vertices by Order-5 or Longer Paths

Abstract

Publication series

Conference

Funding

Research Keywords

Access Output

Other Access Options

Permanent Link

Other Files and Links

Fingerprint

Projects

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

GRF: Algorithms for Searching MS Spectra against Protein Databases and Protein Sequencing Using Combined Top-down and Bottom-up Approach for Monoclonal Antibodies

GRF: Efficient Algorithms for Identification of Modified Proteoforms Using Top-down Mass Spectra

Cite this