zbMATH — the first resource for mathematics

Approximating maximum subgraphs without short cycles. (English) Zbl 1214.05057
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 \(\Omega(n^{-\frac{1}{r}+\frac{1}{r(2r-1)}-\varepsilon})\)-approximation scheme with running time \((1/\varepsilon)^{O(1/\varepsilon)}\mathsf{poly}(n)\), where \(n=|V|\) is the number of vertices in the graph. This improves upon the ratio \(\Omega(n^{-1/r})\) that can be deduced from extremal graph theory. In particular, for \(k=4\) the improvement is from \(\Omega(n^{-1/2})\) to \(\Omega(n^{-1/3-\varepsilon})\).
Our additional result is for odd \(k\). The \(3\)-Cycle Transversal problem (covering all triangles) was studied by M. Krivelevich [Discrete Math. 142, No.1–3, 281–286 (1995; Zbl 0920.05056)], 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 \(\frac{k-1}{2k-3}=\frac{1}{2}+\frac{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-\varepsilon)\)-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 \(\leq k\) or finding a maximum subgraph without cycles of length \(\leq k\) (i.e., with girth \(>k\)).

05C38 Paths and cycles
05C35 Extremal problems in graph theory
68W25 Approximation algorithms
PDF BibTeX Cite
Full Text: DOI