Given an undirected graph G with n nodes and m edges, we address the problem of finding a largest collection of edge-disjoint cycles in G. The problem, dubbed CYCLE PACKING, is very closely related to a few genome rearrangement problems in computational biology. In this paper, we study the complexity and approximability of CYCLE PACKING, about which very little is known although the problem is natural and has practical applications. We show that the problem is APX-hard but can be approximated within a factor of O(log n) by a simple greedy approach. We do not know whether the O(log n) factor is tight, but we give a nontrivial example for which the ratio achieved by greedy is not constant, namely Ω( log n/(log log n)). We also show that, for “not too sparse” graphs, i.e., graphs for which m = Ω(n1+1/t +δ ) for some positive integer t and for any fixed δ > 0, we can achieve an approximation arbitrarily close to 2t/3 in polynomial time. In particular, for any ε > 0, this yields a 4/3 + ε approximation when m = Ω(n3/2+δ ), therefore also for dense graphs. Finally, we briefly discuss a natural linear programming relaxation for the problem.

Packing Cycles in Undirected Graphs

RIZZI, ROMEO
2003-01-01

Abstract

Given an undirected graph G with n nodes and m edges, we address the problem of finding a largest collection of edge-disjoint cycles in G. The problem, dubbed CYCLE PACKING, is very closely related to a few genome rearrangement problems in computational biology. In this paper, we study the complexity and approximability of CYCLE PACKING, about which very little is known although the problem is natural and has practical applications. We show that the problem is APX-hard but can be approximated within a factor of O(log n) by a simple greedy approach. We do not know whether the O(log n) factor is tight, but we give a nontrivial example for which the ratio achieved by greedy is not constant, namely Ω( log n/(log log n)). We also show that, for “not too sparse” graphs, i.e., graphs for which m = Ω(n1+1/t +δ ) for some positive integer t and for any fixed δ > 0, we can achieve an approximation arbitrarily close to 2t/3 in polynomial time. In particular, for any ε > 0, this yields a 4/3 + ε approximation when m = Ω(n3/2+δ ), therefore also for dense graphs. Finally, we briefly discuss a natural linear programming relaxation for the problem.
2003
Packing; Edge-disjoint cycles; Complexity; Approximation; Linear programming relaxation
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11562/409619
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 47
  • ???jsp.display-item.citation.isi??? 40
social impact