TY - GEN
T1 - Approximating maximum subgraphs without short cycles
AU - Kortsarz, Guy
AU - Langberg, Michael
AU - Nutov, Zeev
PY - 2008
Y1 - 2008
N2 - We study approximation algorithms, integrality gaps, and hardness of approximation, of two problems related to cycles of "small" length k in a given graph. The instance for these problems is a graph G = (V,E) and an integer k. The k -Cycle Transversal problem is to find a minimum edge subset of E that intersects every k-cycle. The k -Cycle-Free Subgraph problem is to find a maximum edge subset of E without k-cycles. The 3-Cycle Transversal problem (covering all triangles) was studied by Krivelevich [Discrete Mathematics, 1995], where an LP-based 2-approximation algorithm was presented. The integrality gap of the underlying LP was posed as an open problem in the work of Krivelevich. We resolve this problem by showing a sequence of graphs with integrality gap approaching 2. In addition, we show that if 3-Cycle Transversal admits a (2 - ε)-approximation algorithm, then so does the Vertex-Cover problem, and thus improving the ratio 2 is unlikely. We also show that k -Cycle Transversal admits a (k - 1)-approximation algorithm, which extends the result of Krivelevich from k = 3 to any k. Based on this, for odd k we give an algorithm for k -Cycle-Free Subgraph with ratio k-1/2k-3 = 1/2 + 1/4k-6; this improves over the trivial ratio of 1/2. Our main result however is for the k -Cycle-Free Subgraph problem with even values of k. For any k = 2r, we give an Ω(n - 1/r + 1/r(2r-1)-ε)-approximation scheme with running time ε-Ω(1/ε) poly(n). This improves over the ratio Ω(n -1/r ) that can be deduced from extremal graph theory. In particular, for k = 4 the improvement is from Ω(n -1/2) to Ω(1/n - 1/3 - ε ). Similar results are shown for the problem of covering cycles of length ≤ k or finding a maximum subgraph without cycles of length ≤ k.
AB - We study approximation algorithms, integrality gaps, and hardness of approximation, of two problems related to cycles of "small" length k in a given graph. The instance for these problems is a graph G = (V,E) and an integer k. The k -Cycle Transversal problem is to find a minimum edge subset of E that intersects every k-cycle. The k -Cycle-Free Subgraph problem is to find a maximum edge subset of E without k-cycles. The 3-Cycle Transversal problem (covering all triangles) was studied by Krivelevich [Discrete Mathematics, 1995], where an LP-based 2-approximation algorithm was presented. The integrality gap of the underlying LP was posed as an open problem in the work of Krivelevich. We resolve this problem by showing a sequence of graphs with integrality gap approaching 2. In addition, we show that if 3-Cycle Transversal admits a (2 - ε)-approximation algorithm, then so does the Vertex-Cover problem, and thus improving the ratio 2 is unlikely. We also show that k -Cycle Transversal admits a (k - 1)-approximation algorithm, which extends the result of Krivelevich from k = 3 to any k. Based on this, for odd k we give an algorithm for k -Cycle-Free Subgraph with ratio k-1/2k-3 = 1/2 + 1/4k-6; this improves over the trivial ratio of 1/2. Our main result however is for the k -Cycle-Free Subgraph problem with even values of k. For any k = 2r, we give an Ω(n - 1/r + 1/r(2r-1)-ε)-approximation scheme with running time ε-Ω(1/ε) poly(n). This improves over the ratio Ω(n -1/r ) that can be deduced from extremal graph theory. In particular, for k = 4 the improvement is from Ω(n -1/2) to Ω(1/n - 1/3 - ε ). Similar results are shown for the problem of covering cycles of length ≤ k or finding a maximum subgraph without cycles of length ≤ k.
UR - http://www.scopus.com/inward/record.url?scp=51849143753&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=51849143753&partnerID=8YFLogxK
U2 - https://doi.org/10.1007/978-3-540-85363-3_10
DO - https://doi.org/10.1007/978-3-540-85363-3_10
M3 - Conference contribution
SN - 3540853626
SN - 9783540853626
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 118
EP - 131
BT - Approximation, Randomization and Combinatorial Optimization
T2 - 11th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2008 and 12th International Workshop on Randomization and Computation, RANDOM 2008
Y2 - 25 August 2008 through 27 August 2008
ER -