Abstract
A cycle cover of a graph is a spanning subgraph, each node of which is part of exactly one simple cycle. A k-cycle cover is a cycle cover where each cycle has length at least k. Given a complete directed graph with edge weights zero and one, Max-k-DDC(0,1) is the problem of finding a k-cycle cover with maximum weight. We present a 2/3 approximation algorithm for Max-k-DDC(0,1) with running time O(n 5/2). This algorithm yields a 4/3 approximation algorithm for Max-k-DDC(1,2) as well. Instances of the latter problem are complete directed graphs with edge weights one and two. The goal is to find a k-cycle cover with minimum weight. We particularly obtain a 2/3 approximation algorithm for the asymmetric maximum traveling salesman problem with distances zero and one and a 4/3 approximation algorithm for the asymmetric minimum traveling salesman problem with distances one and two. As a lower bound, we prove that Max-k-DDC(0,1) for k ≥ 3 and Max-k-UCC(0,1) (finding maximum weight cycle covers in undirected graphs) for k ≥ 7 are \APX-complete.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
Author information
Authors and Affiliations
Corresponding authors
Rights and permissions
About this article
Cite this article
Bläser, M., Manthey, B. Approximating Maximum Weight Cycle Covers in Directed Graphs with Weights Zero and One. Algorithmica 42, 121–139 (2005). https://doi.org/10.1007/s00453-004-1131-0
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00453-004-1131-0