Approximation Algorithms for the Directed Path Partition Problems

Yong Chen; Zhi Zhong Chen; Curtis Kennedy; Guohui Lin; Yao Xu; An Zhang

doi:10.1007/978-3-030-97099-4_2

Approximation Algorithms for the Directed Path Partition Problems

Yong Chen, Zhi Zhong Chen, Curtis Kennedy, Guohui Lin, Yao Xu, An Zhang

Computer Science

Research output: Contribution to book or proceeding › Conference article › peer-review

3 Scopus citations

Abstract

Given a digraph G= (V, E), the k-path partition problem is to find a minimum collection of vertex-disjoint directed paths each of order at most k to cover all the vertices of V. The problem has various applications in facility location, network monitoring, transportation and others. Its special case on undirected graphs has received much attention recently, but the general version is seemingly untouched in the literature. We present the first k/2-approximation algorithm, for any k≥ 3, based on a novel concept of augmenting path to minimize the number of singletons in the partition. When k≥ 7, we present an improved (k+ 2 ) / 3 -approximation algorithm based on the maximum path-cycle cover followed by a careful 2-cycle elimination process. When k= 3, we define the second novel kind of augmenting paths to reduce the number of 2-paths and propose an improved 13/9-approximation algorithm.

Original language	English
Title of host publication	Frontiers of Algorithmics - International Joint Conference, IJTCS-FAW 2021, Proceedings
Editors	Jing Chen, Minming Li, Guochuan Zhang
Publisher	Springer Science and Business Media Deutschland GmbH
Pages	23-36
Number of pages	14
ISBN (Print)	9783030970987
DOIs	https://doi.org/10.1007/978-3-030-97099-4_2
State	Published - 2022
Event	15th International Workshop on Frontiers in Algorithmics, FAW 2021, held in conjunction with 2nd International Joint Conference on Theoretical Computer Science, IJTCS-FAW 2021 - Beijing, China Duration: Aug 16 2021 → Aug 19 2021

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	12874 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	15th International Workshop on Frontiers in Algorithmics, FAW 2021, held in conjunction with 2nd International Joint Conference on Theoretical Computer Science, IJTCS-FAW 2021
Country/Territory	China
City	Beijing
Period	08/16/21 → 08/19/21

Keywords

Path partition
approximation algorithm
augmenting path
digraph
matching
path-cycle cover

Access to Document

10.1007/978-3-030-97099-4_2

Cite this

Chen, Y., Chen, Z. Z., Kennedy, C., Lin, G., Xu, Y., & Zhang, A. (2022). Approximation Algorithms for the Directed Path Partition Problems. In J. Chen, M. Li, & G. Zhang (Eds.), Frontiers of Algorithmics - International Joint Conference, IJTCS-FAW 2021, Proceedings (pp. 23-36). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 12874 LNCS). Springer Science and Business Media Deutschland GmbH. https://doi.org/10.1007/978-3-030-97099-4_2

Chen, Yong ; Chen, Zhi Zhong ; Kennedy, Curtis et al. / Approximation Algorithms for the Directed Path Partition Problems. Frontiers of Algorithmics - International Joint Conference, IJTCS-FAW 2021, Proceedings. editor / Jing Chen ; Minming Li ; Guochuan Zhang. Springer Science and Business Media Deutschland GmbH, 2022. pp. 23-36 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{dae0623850854dfcaf38857a41eec9b1,

title = "Approximation Algorithms for the Directed Path Partition Problems",

abstract = "Given a digraph G= (V, E), the k-path partition problem is to find a minimum collection of vertex-disjoint directed paths each of order at most k to cover all the vertices of V. The problem has various applications in facility location, network monitoring, transportation and others. Its special case on undirected graphs has received much attention recently, but the general version is seemingly untouched in the literature. We present the first k/2-approximation algorithm, for any k≥ 3, based on a novel concept of augmenting path to minimize the number of singletons in the partition. When k≥ 7, we present an improved (k+ 2 ) / 3 -approximation algorithm based on the maximum path-cycle cover followed by a careful 2-cycle elimination process. When k= 3, we define the second novel kind of augmenting paths to reduce the number of 2-paths and propose an improved 13/9-approximation algorithm.",

keywords = "Path partition, approximation algorithm, augmenting path, digraph, matching, path-cycle cover",

author = "Yong Chen and Chen, {Zhi Zhong} and Curtis Kennedy and Guohui Lin and Yao Xu and An Zhang",

note = "Publisher Copyright: {\textcopyright} 2022, Springer Nature Switzerland AG.; 15th International Workshop on Frontiers in Algorithmics, FAW 2021, held in conjunction with 2nd International Joint Conference on Theoretical Computer Science, IJTCS-FAW 2021 ; Conference date: 16-08-2021 Through 19-08-2021",

year = "2022",

doi = "10.1007/978-3-030-97099-4_2",

language = "English",

isbn = "9783030970987",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Science and Business Media Deutschland GmbH",

pages = "23--36",

editor = "Jing Chen and Minming Li and Guochuan Zhang",

booktitle = "Frontiers of Algorithmics - International Joint Conference, IJTCS-FAW 2021, Proceedings",

address = "Germany",

}

Chen, Y, Chen, ZZ, Kennedy, C, Lin, G, Xu, Y & Zhang, A 2022, Approximation Algorithms for the Directed Path Partition Problems. in J Chen, M Li & G Zhang (eds), Frontiers of Algorithmics - International Joint Conference, IJTCS-FAW 2021, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 12874 LNCS, Springer Science and Business Media Deutschland GmbH, pp. 23-36, 15th International Workshop on Frontiers in Algorithmics, FAW 2021, held in conjunction with 2nd International Joint Conference on Theoretical Computer Science, IJTCS-FAW 2021, Beijing, China, 08/16/21. https://doi.org/10.1007/978-3-030-97099-4_2

Approximation Algorithms for the Directed Path Partition Problems. / Chen, Yong; Chen, Zhi Zhong; Kennedy, Curtis et al.
Frontiers of Algorithmics - International Joint Conference, IJTCS-FAW 2021, Proceedings. ed. / Jing Chen; Minming Li; Guochuan Zhang. Springer Science and Business Media Deutschland GmbH, 2022. p. 23-36 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 12874 LNCS).

Research output: Contribution to book or proceeding › Conference article › peer-review

TY - GEN

T1 - Approximation Algorithms for the Directed Path Partition Problems

AU - Chen, Yong

AU - Chen, Zhi Zhong

AU - Kennedy, Curtis

AU - Lin, Guohui

AU - Xu, Yao

AU - Zhang, An

PY - 2022

Y1 - 2022

N2 - Given a digraph G= (V, E), the k-path partition problem is to find a minimum collection of vertex-disjoint directed paths each of order at most k to cover all the vertices of V. The problem has various applications in facility location, network monitoring, transportation and others. Its special case on undirected graphs has received much attention recently, but the general version is seemingly untouched in the literature. We present the first k/2-approximation algorithm, for any k≥ 3, based on a novel concept of augmenting path to minimize the number of singletons in the partition. When k≥ 7, we present an improved (k+ 2 ) / 3 -approximation algorithm based on the maximum path-cycle cover followed by a careful 2-cycle elimination process. When k= 3, we define the second novel kind of augmenting paths to reduce the number of 2-paths and propose an improved 13/9-approximation algorithm.

AB - Given a digraph G= (V, E), the k-path partition problem is to find a minimum collection of vertex-disjoint directed paths each of order at most k to cover all the vertices of V. The problem has various applications in facility location, network monitoring, transportation and others. Its special case on undirected graphs has received much attention recently, but the general version is seemingly untouched in the literature. We present the first k/2-approximation algorithm, for any k≥ 3, based on a novel concept of augmenting path to minimize the number of singletons in the partition. When k≥ 7, we present an improved (k+ 2 ) / 3 -approximation algorithm based on the maximum path-cycle cover followed by a careful 2-cycle elimination process. When k= 3, we define the second novel kind of augmenting paths to reduce the number of 2-paths and propose an improved 13/9-approximation algorithm.

KW - Path partition

KW - approximation algorithm

KW - augmenting path

KW - digraph

KW - matching

KW - path-cycle cover

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

U2 - 10.1007/978-3-030-97099-4_2

DO - 10.1007/978-3-030-97099-4_2

M3 - Conference article

AN - SCOPUS:85126540582

SN - 9783030970987

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 23

EP - 36

BT - Frontiers of Algorithmics - International Joint Conference, IJTCS-FAW 2021, Proceedings

A2 - Chen, Jing

A2 - Li, Minming

A2 - Zhang, Guochuan

PB - Springer Science and Business Media Deutschland GmbH

T2 - 15th International Workshop on Frontiers in Algorithmics, FAW 2021, held in conjunction with 2nd International Joint Conference on Theoretical Computer Science, IJTCS-FAW 2021

Y2 - 16 August 2021 through 19 August 2021

ER -

Chen Y, Chen ZZ, Kennedy C, Lin G, Xu Y, Zhang A. Approximation Algorithms for the Directed Path Partition Problems. In Chen J, Li M, Zhang G, editors, Frontiers of Algorithmics - International Joint Conference, IJTCS-FAW 2021, Proceedings. Springer Science and Business Media Deutschland GmbH. 2022. p. 23-36. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-030-97099-4_2