Saarland University
Department of Computer Science
Computational Complexity
Computational Complexity




Computational Complexity - Research Seminar

Bodo Manthey: Approximation Algorithms for Restricted Cycle Covers Based on Cycle Decompositions

June 14, 2006, 10:15 a.m.
E 1 3, Room 415

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. To do this, we develop a general decomposition technique for cycle covers.

Finally, we show tight lower bounds for the approximation ratios achieved by algorithms based on such decomposition techniques.