Access the full text.
Sign up today, get DeepDyve free for 14 days.
D. Dor, M. Tarsi (1997)
Graph Decomposition is NP-Complete: A Complete Proof of Holyer's ConjectureSIAM J. Comput., 26
M. Hajiaghayi, F. Leighton (2006)
On the max-flow min-cut ratio for directed multicommodity flowsTheor. Comput. Sci., 352
R. Raz (1995)
A parallel repetition theorem
Sanjeev Arora, C. Lund, R. Motwani, M. Sudan, M. Szegedy (1992)
Proof verification and hardness of approximation problemsProceedings., 33rd Annual Symposium on Foundations of Computer Science
V. Bafna, P. Berman, Toshihiro Fujito (1995)
Constant Ratio Approximations of the Weighted Feedback Vertex Set Problem for Undirected Graphs
B. Bollobás, P. Erdös, M. Simonovits, E. Szemerédi (1978)
Extremal Graphs without Large Forbidden SubgraphsAnnals of discrete mathematics, 3
C. Chekuri, S. Khanna (2003)
Edge disjoint paths revisitedACM Transactions on Algorithms (TALG), 3
P. Seymour (1995)
Packing directed circuits fractionallyCombinatorica, 15
Fabián Chudak, M. Goemans, D. Hochbaum, David Williamson (1998)
A primal-dual interpretation of two 2-approximation algorithms for the feedback vertex set problem in undirected graphsOper. Res. Lett., 22
Lecture Notes in Computer Science
Bin Ma, Lusheng Wang (2000)
On the Inapproximability of Disjoint Paths and Minimum Steiner Forest with Bandwidth ConstraintsJ. Comput. Syst. Sci., 60
Kasturi Varadarajan, G. Venkataraman (2004)
Graph decomposition and a greedy algorithm for edge-disjoint paths
Wiss. Z. Tech. Rep. Martin-Luther Univ. Halle-Wittenberg Math.-Natur. Reihe
J. Komlos (1997)
Covering odd cyclesCombinatorica, 17
M. Andrews, Julia Chuzhoy, S. Khanna, Lisa Zhang (2005)
Hardness of the undirected edge-disjoint paths problem with congestion46th Annual IEEE Symposium on Foundations of Computer Science (FOCS'05)
D. Dor, M. Tarsi (1992)
Graph decomposition is NPC - a complete proof of Holyer's conjecture
F. Lazebnik, V. Ustimenko, A. Woldar (1996)
New upper bounds on the order of cagesElectron. J. Comb., 4
A. Becker, D. Geiger (1994)
Approximation Algorithms for the Loop Cutset ProblemArXiv, abs/1302.6787
V. Guruswami, S. Khanna, R. Rajaraman, B. Shepherd, M. Yannakakis (1999)
Near-optimal hardness results and approximation algorithms for edge-disjoint paths and related problemsJ. Comput. Syst. Sci., 67
Paul Erd, H. Sachs (1963)
Regukre Graphen gegebener Taillenweite mit minimaler Knotenzahl
Sanjeev Arora, S. Safra (1998)
Probabilistic checking of proofs: a new characterization of NPJ. ACM, 45
C. Chekuri, S. Khanna, F. Shepherd (2006)
An O(sqrt(n)) Approximation and Integrality Gap for Disjoint Paths and Unsplittable FlowTheory Comput., 2
(2006)
Article 48, Publication date
ACM Journal Name
(2007)
Discrete Math. 3, 29–41
Under a stronger complexity assumption that for some sufficiently small σ > 0, NP ⊆ DTIME(2 n σ ), we can improve the hardness result to ( log n (log log n) 2 )
G. Andrews, R. Roy (1996)
Ramanujan's method in q-series congruencesElectron. J. Comb., 4
A. Caprara, A. Panconesi, Romeo Rizzi (2003)
Packing cycles in undirected graphsJ. Algorithms, 48
P. Balister (2003)
Packing Digraphs with Directed Closed TrailsCombinatorics, Probability and Computing, 12
B. Bollobás, A. Thomason (1997)
On the girth of hamiltonian weakly pancyclic graphsJ. Graph Theory, 26
G. Even, J. Naor, B. Schieber, M. Sudan (1998)
Approximating Minimum Feedback Sets and Multicuts in Directed GraphsAlgorithmica, 20
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 Θ(&sqrt;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 &sqrt; n -approximation algorithm. Finally, we give an O ( n 2/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 (log 1 − ε n ) for any constant ε > 0. This improves upon the previously known APX-hardness result for this problem.
ACM Transactions on Algorithms (TALG) – Association for Computing Machinery
Published: Nov 1, 2007
Read and print from thousands of top scholarly journals.
Already have an account? Log in
Bookmark this article. You can see your Bookmarks on your DeepDyve Library.
To save an article, log in first, or sign up for a DeepDyve account if you don’t already have one.
Copy and paste the desired citation format or use the link below to download a file formatted for EndNote
Access the full text.
Sign up today, get DeepDyve free for 14 days.
All DeepDyve websites use cookies to improve your online experience. They were placed on your computer when you launched this website. You can change your cookie settings through your browser.