TY - JOUR

T1 - Approximating maximum subgraphs without short cycles

AU - Kortsarz, Guy

AU - Langberg, Michael

AU - Nutov, Zeev

N1 - Copyright:
Copyright 2010 Elsevier B.V., All rights reserved.

PY - 2010

Y1 - 2010

N2 - We study approximation algorithms, integrality gaps, and hardness of approximation of two problems related to cycles of "small" length k in a given (undirected) graph. The instance for these problems consists of 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. Our main result is for the k-Cycle-Free Subgraph problem with even values of k. For any k = 2r, we give an o(n-1/r + 1/r(2r-1)-ε)-approximation scheme with running time (1/ε)O(1/ε)poly(n), where n = |V | is the number of vertices in the graph. This improves upon 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 ω(n-1/3-ε). Our additional result is for odd k. The 3-Cycle Transversal problem (covering all triangles) was studied by Krivelevich [Discrete Math., 142 (1995), pp. 281-286], who presented an LP-based 2-approximation algorithm. We show that k-Cycle Transversal admits a (k - 1)-approximation algorithm, which extends to any odd k the result that Krivelevich proved for k = 3. 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 upon the trivial ratio of 1/2. For k = 3, 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 k-Cycle Transversal admits a (2 - ε)- approximation algorithm, then so does the Vertex-Cover problem; thus improving the ratio 2 is unlikely. Similar results are shown for the problem of covering cycles of length ≤ k or finding a maximum subgraph without cycles of length ≤ k (i.e., with girth > 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 (undirected) graph. The instance for these problems consists of 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. Our main result is for the k-Cycle-Free Subgraph problem with even values of k. For any k = 2r, we give an o(n-1/r + 1/r(2r-1)-ε)-approximation scheme with running time (1/ε)O(1/ε)poly(n), where n = |V | is the number of vertices in the graph. This improves upon 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 ω(n-1/3-ε). Our additional result is for odd k. The 3-Cycle Transversal problem (covering all triangles) was studied by Krivelevich [Discrete Math., 142 (1995), pp. 281-286], who presented an LP-based 2-approximation algorithm. We show that k-Cycle Transversal admits a (k - 1)-approximation algorithm, which extends to any odd k the result that Krivelevich proved for k = 3. 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 upon the trivial ratio of 1/2. For k = 3, 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 k-Cycle Transversal admits a (2 - ε)- approximation algorithm, then so does the Vertex-Cover problem; thus improving the ratio 2 is unlikely. Similar results are shown for the problem of covering cycles of length ≤ k or finding a maximum subgraph without cycles of length ≤ k (i.e., with girth > k).

KW - Approximation

KW - Cycles of length k

KW - Girth

KW - LP

KW - Packing

UR - http://www.scopus.com/inward/record.url?scp=77952517549&partnerID=8YFLogxK

U2 - 10.1137/09074944X

DO - 10.1137/09074944X

M3 - ???researchoutput.researchoutputtypes.contributiontojournal.article???

AN - SCOPUS:77952517549

SN - 0895-4801

VL - 24

SP - 255

EP - 269

JO - SIAM Journal on Discrete Mathematics

JF - SIAM Journal on Discrete Mathematics

IS - 1

ER -