A cycle cover of a directed graph is a collection of node disjoint cycles such that every node is part of exactly one cycle.
A
k-cycle cover is a cycle cover in which every cycle has length at least
k. While deciding whether a directed graph has a 2-cycle cover is solvable in polynomial time, deciding whether it has a 3-cycle
cover is already NP-complete. Given a directed graph with nonnegative edge weights, a maximum weight 2-cycle cover can be
computed in polynomial time, too. We call the corresponding optimization problem of finding a maximum weight 3-cycle cover
Max-3-DCC.
In this paper we present two polynomial time approximation algorithms for Max-3-DCC. The heavier of the 3-cycle covers computed
by these algorithms has at least a fraction of
for any ∈> 0, of the weight of a maximum weight 3-cycle cover.
As a lower bound, we prove that Max-3-DCC is APX-complete, even if the weights fulfil the triangle inequality.