Computational Biology CB_W0008

Title : Disjoint Cycles: Integrality Gap, Hardness, and Approximation
Author : Mohammad R. Salavatipour and Jacques Verstraete
Year : 2005
Place of publish : SpringLink
Abstract :
 In the edge-disjoint cycle packing problem we are given a graph G and we have to find a largest set of edge-disjoint cycles in G. The problem of packing vertex-disjoint cycles in G is defined similarly. The best approximation algorithms for edge-disjoint cycle packing are due to Krivelevich et al. [16], where they give an OÖ{log n}Ologn -approximation for undirected graphs and an O(Ön)O(n) -approximation for directed graphs. They also conjecture that the problem in directed case has an integrality gap of W(Ö{n})(n) . No non-trivial lower bound is known for the integrality gap of this problem. Here we show that both problems of packing edge-disjoint and packing vertex-disjoint cycles in a directed graph have an integrality gap of W(\fraclog nlog log n)(lognloglogn). This is the first super constant lower bound for the integrality gap of these problems. We also prove that both problems are quasi-NP-hard to approximate within a factor of O(log1?-?-? e n), for any e > 0. For the problem of packing vertex-disjoint cycles, we give the first approximation algorithms with ratios O(log n) (for undirected graphs) and O(Ön)O(n)  (for directed graphs). Our algorithms work for the more general case where we have a capacity c v on every vertex v and we are seeking a largest set C of cycles such that at most c v cycles of C contain v.