Packing cycles in undirected graphs Export

@article{citeulike:1832811, 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 , is very closely related to a few genome rearrangement problems in computational biology. In this paper, we study the complexity and approximability of , about which very little is known although the problem is natural and has practical applications. We show that the problem is -hard but can be approximated within a factor of O(logn) by a simple greedy approach. We do not know whether the O(logn) factor is tight, but we give a nontrivial example for which the ratio achieved by greedy is not constant, namely . We also show that, for "not too sparse" graphs, i.e., graphs for which m=[Omega](n1+1/t+[delta]) for some positive integer t and for any fixed [delta]>0, we can achieve an approximation arbitrarily close to 2t/3 in polynomial time. In particular, for any [var epsilon]>0, this yields a 4/3+[var epsilon] approximation when m=[Omega](n3/2+[delta]), therefore also for dense graphs. Finally, we briefly discuss a natural linear programming relaxation for the problem.}, author = {Caprara, Alberto and Panconesi, Alessandro and Rizzi, Romeo}, booktitle = {Twelfth Annual ACM-SIAM Symposium on Discrete Algorithms}, citeulike-article-id = {1832811}, citeulike-linkout-0 = {http://dx.doi.org/10.1016/S0196-6774(03)00052-X}, citeulike-linkout-1 = {http://www.sciencedirect.com/science/article/B6WH3-48NBXJW-4/2/97f332796028e973f89f306936f3031c}, doi = {10.1016/S0196-6774(03)00052-X}, journal = {Journal of Algorithms}, keywords = {approximation, cycle\_packing}, month = {August}, number = {1}, pages = {239--256}, posted-at = {2007-10-28 18:49:32}, priority = {2}, title = {Packing cycles in undirected graphs}, url = {http://dx.doi.org/10.1016/S0196-6774(03)00052-X}, volume = {48}, year = {2003} }

TY - JOUR ID - citeulike:1832811 L3 - citeulike-article-id:1832811 N2 - 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 , is very closely related to a few genome rearrangement problems in computational biology. In this paper, we study the complexity and approximability of , about which very little is known although the problem is natural and has practical applications. We show that the problem is -hard but can be approximated within a factor of O(logn) by a simple greedy approach. We do not know whether the O(logn) factor is tight, but we give a nontrivial example for which the ratio achieved by greedy is not constant, namely . We also show that, for "not too sparse" graphs, i.e., graphs for which m=[Omega](n1+1/t+[delta]) for some positive integer t and for any fixed [delta]>0, we can achieve an approximation arbitrarily close to 2t/3 in polynomial time. In particular, for any [var epsilon]>0, this yields a 4/3+[var epsilon] approximation when m=[Omega](n3/2+[delta]), therefore also for dense graphs. Finally, we briefly discuss a natural linear programming relaxation for the problem. IS - 1 JF - Journal of Algorithms EP - 256 TI - Packing cycles in undirected graphs VL - 48 T2 - Twelfth Annual ACM-SIAM Symposium on Discrete Algorithms SP - 239 KW - approximation KW - cycle_packing AU - Caprara, Alberto AU - Panconesi, Alessandro AU - Rizzi, Romeo PY - 2003/08// UR - http://dx.doi.org/10.1016/S0196-6774(03)00052-X ER -