New for: D1, D2, D3, D4, D5
We come close to settling the complexity and approximability of computing L-cycle covers. On the one hand, we show that for almost all L, computing L-cycle covers of maximum weight in directed and undirected graphs is hard to approximate, and deciding whether a graph contains an L-cycle cover is NP-hard. Most of our hardness results hold even if the edge weights are restricted to be zero or one. On the other hand, we show that the problem of computing L-cycle covers of maximum weight can be approximated with a factor of 2.5 for undirected graphs and with a factor of 3 in the case of directed graphs. These approximation algorithms work for arbitrary sets L.