Approximation algorithms for the maximum path cover problem using long paths

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

doi:10.1016/j.ic.2025.105378

Approximation algorithms for the maximum path cover problem using long paths

Mingyang Gong
, Yong Chen
, Zhi-Zhong Chen
, Guohui Lin^*
, Bing Su^*
, 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

16 Downloads (CityUHK Scholars)

Abstract

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 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.4394k + 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.

© 2025 The Author(s). Published by Elsevier Inc.

Original language	English
Article number	105378
Number of pages	19
Journal	Information and Computation
Volume	307
Online published	10 Nov 2025
DOIs	https://doi.org/10.1016/j.ic.2025.105378
Publication status	Published - Nov 2025

Funding

The 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 18K11183), the National Natural Science Foundation of China (Grants 12471301, 61972329 and 72301205), the Ministry of Science and Technology of China (Grant G2023016016L), and the GRF of Hong Kong SAR, China (Grants CityU 11218423, CityU11218821).

Research Keywords

Approximation algorithm
Local search
Path cover
Path-cycle 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.ic.2025.105378

380515704.pdfFinal Published version, 1.48 MBLicence: CC BY

Other Access Options

Check CityUHK Library

Permanent Link

Right click to copy link

Cite this

@article{01dbecbc687d495a8ca6bba4600cfdb6,

title = "Approximation algorithms for the maximum path cover problem using long paths",

abstract = "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 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.4394k + 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. {\textcopyright} 2025 The Author(s). Published by Elsevier Inc. ",

keywords = "Approximation algorithm, Local search, Path cover, Path-cycle cover, Recursion",

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

year = "2025",

month = nov,

doi = "10.1016/j.ic.2025.105378",

language = "English",

volume = "307",

journal = "Information and Computation",

issn = "0890-5401",

publisher = "Elsevier Inc.",

}

TY - JOUR

T1 - Approximation algorithms for the maximum path cover problem using long paths

AU - Gong, Mingyang

AU - Chen, Yong

AU - Chen, Zhi-Zhong

AU - Lin, Guohui

AU - Su, Bing

AU - Wang, Lusheng

PY - 2025/11

Y1 - 2025/11

N2 - 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 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.4394k + 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. © 2025 The Author(s). Published by Elsevier Inc.

AB - 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 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.4394k + 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. © 2025 The Author(s). Published by Elsevier Inc.

KW - Approximation algorithm

KW - Local search

KW - Path cover

KW - Path-cycle cover

KW - Recursion

UR - https://www.scopus.com/pages/publications/105023835173

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

U2 - 10.1016/j.ic.2025.105378

DO - 10.1016/j.ic.2025.105378

M3 - RGC 21 - Publication in refereed journal

SN - 0890-5401

VL - 307

JO - Information and Computation

JF - Information and Computation

M1 - 105378

ER -

Approximation algorithms for the maximum path cover problem using long 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

Approximation algorithms for the maximum path cover problem using long 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