Approximation algorithms for restricted cycle covers based on cycle decompositions

Bodo Manthey

doi:10.1007/11917496_30

Approximation algorithms for restricted cycle covers based on cycle decompositions

Bodo Manthey^*

^*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

Abstract

A cycle cover of a graph is a set of cycles such that every vertex is part of exactly one cycle. An L-cycle cover is a cycle cover in which the length of every cycle is in the set L ⊆ ℕ. For most sets L, the problem of computing L-cycle covers of maximum weight is NP-hard and APX-hard. We devise polynomial-time approximation algorithms for L-cycle covers. More precisely, we present a factor 2 approximation algorithm for computing L-cycle covers of maximum weight in undirected graphs and a factor 20/7 approximation algorithm for the same problem in directed graphs. Both algorithms work for arbitrary sets L. To do this, we develop a general decomposition technique for cycle covers. Finally, we show tight lower bounds for the approximation ratios achievable by algorithms based on such decomposition techniques.

Original language	English
Title of host publication	Graph-Theoretic Concepts in Computer Science
Subtitle of host publication	32nd International Workshop, WG 2006, Bergen, Norway, June 22-24, 2006 Revised Papers
Editors	Fedor V. Fomin
Place of Publication	Berlin, Heidelberg
Publisher	Springer
Pages	336-347
Number of pages	12
ISBN (Electronic)	978-3-540-48382-3
ISBN (Print)	978-3-540-48381-6
DOIs	https://doi.org/10.1007/11917496_30
Publication status	Published - 1 Jan 2006
Externally published	Yes
Event	32nd International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2006 - Bergen, Norway Duration: 22 Jun 2006 → 24 Jun 2006 Conference number: 32

Publication series

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

Workshop

Workshop	32nd International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2006
Abbreviated title	WG
Country/Territory	Norway
City	Bergen
Period	22/06/06 → 24/06/06

Access to Document

10.1007/11917496_30

Cite this

@inproceedings{fc1be846af354250b941b594d0fd4c27,

title = "Approximation algorithms for restricted cycle covers based on cycle decompositions",

abstract = "A cycle cover of a graph is a set of cycles such that every vertex is part of exactly one cycle. An L-cycle cover is a cycle cover in which the length of every cycle is in the set L ⊆ ℕ. For most sets L, the problem of computing L-cycle covers of maximum weight is NP-hard and APX-hard. We devise polynomial-time approximation algorithms for L-cycle covers. More precisely, we present a factor 2 approximation algorithm for computing L-cycle covers of maximum weight in undirected graphs and a factor 20/7 approximation algorithm for the same problem in directed graphs. Both algorithms work for arbitrary sets L. To do this, we develop a general decomposition technique for cycle covers. Finally, we show tight lower bounds for the approximation ratios achievable by algorithms based on such decomposition techniques.",

author = "Bodo Manthey",

year = "2006",

month = jan,

day = "1",

doi = "10.1007/11917496\_30",

language = "English",

isbn = "978-3-540-48381-6",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "336--347",

editor = "Fomin, \{Fedor V.\}",

booktitle = "Graph-Theoretic Concepts in Computer Science",

address = "Germany",

note = "32nd International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2006, WG ; Conference date: 22-06-2006 Through 24-06-2006",

}

Manthey, B 2006, Approximation algorithms for restricted cycle covers based on cycle decompositions. in FV Fomin (ed.), Graph-Theoretic Concepts in Computer Science: 32nd International Workshop, WG 2006, Bergen, Norway, June 22-24, 2006 Revised Papers. Lecture Notes in Computer Science, vol. 4271, Springer, Berlin, Heidelberg, pp. 336-347, 32nd International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2006, Bergen, Norway, 22/06/06. https://doi.org/10.1007/11917496_30

Approximation algorithms for restricted cycle covers based on cycle decompositions. / Manthey, Bodo.
Graph-Theoretic Concepts in Computer Science: 32nd International Workshop, WG 2006, Bergen, Norway, June 22-24, 2006 Revised Papers. ed. / Fedor V. Fomin. Berlin, Heidelberg: Springer, 2006. p. 336-347 (Lecture Notes in Computer Science; Vol. 4271).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - Approximation algorithms for restricted cycle covers based on cycle decompositions

AU - Manthey, Bodo

N1 - Conference code: 32

PY - 2006/1/1

Y1 - 2006/1/1

N2 - A cycle cover of a graph is a set of cycles such that every vertex is part of exactly one cycle. An L-cycle cover is a cycle cover in which the length of every cycle is in the set L ⊆ ℕ. For most sets L, the problem of computing L-cycle covers of maximum weight is NP-hard and APX-hard. We devise polynomial-time approximation algorithms for L-cycle covers. More precisely, we present a factor 2 approximation algorithm for computing L-cycle covers of maximum weight in undirected graphs and a factor 20/7 approximation algorithm for the same problem in directed graphs. Both algorithms work for arbitrary sets L. To do this, we develop a general decomposition technique for cycle covers. Finally, we show tight lower bounds for the approximation ratios achievable by algorithms based on such decomposition techniques.

AB - A cycle cover of a graph is a set of cycles such that every vertex is part of exactly one cycle. An L-cycle cover is a cycle cover in which the length of every cycle is in the set L ⊆ ℕ. For most sets L, the problem of computing L-cycle covers of maximum weight is NP-hard and APX-hard. We devise polynomial-time approximation algorithms for L-cycle covers. More precisely, we present a factor 2 approximation algorithm for computing L-cycle covers of maximum weight in undirected graphs and a factor 20/7 approximation algorithm for the same problem in directed graphs. Both algorithms work for arbitrary sets L. To do this, we develop a general decomposition technique for cycle covers. Finally, we show tight lower bounds for the approximation ratios achievable by algorithms based on such decomposition techniques.

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

U2 - 10.1007/11917496_30

DO - 10.1007/11917496_30

M3 - Conference contribution

AN - SCOPUS:33845520498

SN - 978-3-540-48381-6

T3 - Lecture Notes in Computer Science

SP - 336

EP - 347

BT - Graph-Theoretic Concepts in Computer Science

A2 - Fomin, Fedor V.

PB - Springer

CY - Berlin, Heidelberg

T2 - 32nd International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2006

Y2 - 22 June 2006 through 24 June 2006

ER -

Approximation algorithms for restricted cycle covers based on cycle decompositions

Abstract

Publication series

Workshop

Access to Document

Other files and links

Fingerprint

Cite this