Michael Krivelevich
Abstract
The cycle packing number νe(G) of a graph G is the maximum number of pairwise edge-disjoint cycles in G. Computing νe(G) is an NP-hard problem. We present approximation algorithms for computing νe(G) in both undirected and directed graphs. In the undirected case we analyze a variant of the modified greedy algorithm suggested by Caprara et al. [2003] and show that it has approximation ratio Θ(√log n), where n = |V(G)|. This improves upon the previous O(log n) upper bound for the approximation ratio of this algorithm. In the directed case we present a √n-approximation algorithm. Finally, we give an O(n2/3)-approximation algorithm for the problem of finding a maximum number of edge-disjoint cycles that intersect a specified subset S of vertices. We also study generalizations of these problems. Our approximation ratios are the currently best-known ones and, in addition, provide upper bounds on the integrality gap of standard LP-relaxations of these problems. In addition, we give lower bounds for the integrality gap and approximability of νe(G) in directed graphs. Specifically, we prove a lower bound of Ω(log n/loglog n) for the integrality gap of edge-disjoint cycle packing. We also show that it is quasi-NP-hard to approximate νe(G) within a factor of O(log1 − ε n) for any constant ε > 0. This improves upon the previously known APX-hardness result for this problem.
- Andrews, M., Chuzhoy, J., and Zhang, L. 2005. Hardness of the undirected edge-disjoint paths problem with congestion. In Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS). IEEE Computer Society, Washington, DC, 226--244. Google Scholar
Digital Library
- Arora, S., Lund, C., Motwani, R., Sudan, M., and Szegedy, M. 1998. Proof verification and the hardness of approximation problems. J. ACM 45, 3, 501--555. Google ScholarDigital Library
- Arora, S., and Safra, S. 1998. Probabilistic checking of proofs: A new characterization of np. J. ACM 45, 1, 70--122. Google ScholarDigital Library
- Bafna, V., Berman, P., and Fujito, T. 1995. Constant ratio approximation of the weighted feedback vertex set problem for undirected graphs. In Proceedings of the 6th International Symposium Algorithms and Computation (ISAAC). Lecture Notes in Computer Science Springer, 142--151. Google ScholarDigital Library
- Balister, P. 2003. Packing digraphs with directed closed trails. Comb. Probab. Comput. 12, 1, 1--15. Google ScholarDigital Library
- Becker, A., and Geiger, D. 1994. Approximation algorithms for the loop cutset problem. In Proceedings of the 10th Annual Conference on Uncertainty in Artificial Intelligence (July 29--31, Seattle, WA). 60--68.Google Scholar
- Bollobás, B. 2004. Extremal Graph Theory. Dover, New York. Google ScholarDigital Library
- Bollobás, B., Erdős, P., Simonovits, M., and Szemerédi, E. 1978. Extremal graphs without large forbidden subgraphs. Ann. Discrete Math. 3, 29--41.Google ScholarCross Ref
- Bollobás, B., and Thomason, A. 1997. On the girth of Hamiltonian weakly pancyclic graphs. J. Graph Theory 26, 3, 165--173. Google ScholarDigital Library
- Caprara, A., Panconesi, A., and Rizzi, R. 2003. Packing cycles in undirected graphs. J. Alg. 48, 1, 239--256. Google ScholarDigital Library
- Chekuri, C., and Khanna, S. 2003. Edge disjoint paths revisited. In Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). Society for Industrial and Applied Mathematics, Philadelphia, PA, 628--637. Google ScholarDigital Library
- Chekuri, C., Khanna, S., and Shepherd, B. 2006. An o(&sqrt;n) approximation and integrality gap for disjoint paths and UFP. Theory Comput. 2, 137--146.Google ScholarCross Ref
- Chudak, F. A., Goemans, M. X., Hochbaum, D. S., and Williamson, D. P. 1998. A primal-dual interpretation of two 2-approximation algorithms for the feedback vertex set problem in undirected graphs. Oper. Res. Lett. 22, 4-5, 111--118. Google ScholarDigital Library
- Dor, D., and Tarsi, M. 1992. Graph decomposition is npc---A complete proof of Holyer's conjecture. In Proceedings of the 24th Annual ACM Symposium on Theory of Computing (STOC). ACM Press, New York, 252--263. Google ScholarDigital Library
- Erdős, P., and Sachs, H. 1963. Regulare graphen gegebener taillenweite mit minimaler knotenzahl. Wiss. Z. Tech. Rep. Martin-Luther Univ. Halle-Wittenberg Math.-Natur. Reihe 12.Google Scholar
- Even, G., Naor, J., Schieber, B., and Sudan, M. 1998. Approximating minimum feedback sets and multicuts in directed graphs. Algorithmica 20, 2, 151--174.Google ScholarCross Ref
- Friggstad, Z., and Salavatipour, M. 2006. unpublished manuscript.Google Scholar
- Guruswami, V., Khanna, S., Rajaraman, R., Shepherd, B., and Yannakakis, M. 2003. Near-Optimal hardness results and approximation algorithms for edge-disjoint paths and related problems. J. Comput. Syst. Sci. 67, 3, 473--496. Google ScholarDigital Library
- Hajiaghayi, M. T., and Leighton, T. 2006. On the max-flow min-cut ratio for directed multicommodity flows. Theor. Comput. Sci. 352, 1, 318--321. Google ScholarDigital Library
- Komlós, J. 1997. Covering odd cycles. Combinatorica 17, 3, 393--400.Google ScholarCross Ref
- Lazebnik, F., Ustimenko, V. A., and Woldar, A. J. 1997. New upper bounds on the order of cages. Electr. J. Comb. 4, 2.Google Scholar
- Ma, B., and Wang, L. 2000. On the inapproximability of disjoint paths and minimum steiner forest with bandwidth constraints. J. Comput. Syst. Sci. 60, 1, 1--12. Google ScholarDigital Library
- Raz, R. 1998. A parallel repetition theorem. SIAM J. Comput. 27, 3, 763--803. Google ScholarDigital Library
- Seymour, P. D. 1995. Packing directed circuits fractionally. Combinatorica 15, 2, 281--288.Google ScholarCross Ref
- Varadarajan, K., and Venkataraman, G. 2004. Graph decomposition and a greedy algorithm for edge-disjoint paths. In Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 379--380. Google ScholarDigital Library
Index Terms
- Approximation algorithms and hardness results for cycle packing problems
Recommendations
Hardness and approximation results for packing steiner trees
We study approximation algorithms and hardness of approximation for several versions of the problem of packing Steiner trees. For packing edge-disjoint Steiner trees of undirected graphs, we show APX-hardness for four terminals. For packing Steiner-node-...
Approximation algorithms and hardness results for the clique packing problem
For a fixed family F of graphs, an F-packing in a graph G is a set of pairwise vertex-disjoint subgraphs of G, each isomorphic to an element of F. Finding an F-packing that maximizes the number of covered edges is a natural generalization of the maximum ...
Approximation Algorithms and Hardness Results for Packing Element-Disjoint Steiner Trees in Planar Graphs
We study the problem of packing element-disjoint Steiner trees in graphs. We are given a graph and a designated subset of terminal nodes, and the goal is to find a maximum cardinality set of element-disjoint trees such that each tree contains every ...
Comments