Approximating maximum subgraphs without short cycles.

*(English)*Zbl 1214.05057We 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\)).

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\)).