Abstract
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 \(\frac{k-1}{2k-3}=\frac{1}{2}+\frac{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 \(\Omega\left(n^{-\frac{1}{r}+\frac{1}{r(2r-1)}-\varepsilon}\right)\)-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.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Alon, N.: Bipartite subgraphs. Combinatorica 16, 301–311 (1996)
Alon, N., Bollobás, B., Krivelevich, M., Sudakov, B.: Maximum cuts and judicious partitions in graphs without short cycles. J. of Comb. Th. B 88(2), 329–346 (2003)
Alon, N., Yuster, R., Zwick, U.: Finding and counting given length cycles. Algorithmica 17(3), 209–223 (1997)
Bondy, J.A., Simonovits, M.: Cycles of even lengths in graphs. J. Comb. Th. B 16, 97–105 (1974)
Erdös, P.: Extremal problems in graph theory. In: Fiedler, M. (ed.) Theory of Graphs and Its Applications. Academic Press, New York (1965)
Erdös, P., Gallai, T., Tuza, Z.: Covering and independence in triangle structures. Discrete Mathematics 150, 89–101 (1996)
Feige, U., Langberg, M., Schechtman, G.: Graphs with tiny vector chromatic numbers and huge chromatic numbers. SIAM J. Comput. 33(6), 1338–1368 (2004)
Furedi, Z., Naor, A., Verstraëte, J.: On the Turan number of the hexagon. Advances in Mathematics 203(2), 476–496 (2006)
Goemans, M.X., Williamson, D.P.: Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. J. ACM 42(6), 1115–1145 (1995)
Hoory, S.: The size of bipartite graphs with a given girth. Journal of Combinatorial Theory Series B 86(2), 215–220 (2002)
Komlós, J.: Covering odd cycles. Combinatorica 17(3), 393–400 (1997)
Krivelevich, M.: On a conjecture of Tuza about packing and covering of triangles. Discrete Mathematics 142(1-3), 281–286 (1995)
Kühn, D., Osthus, D.: Four-cycles in graphs without a given even cycle. Journal of Graph Theory 48(2), 147–156 (2005)
Lam, T.: A result on 2k-cycle free bipartite graphs. Australasian Journal of Combinatorics 32, 163–170 (2005)
Lam, T., Verstraëte, J.: A note on graphs without short even cycles. The Electronic Journal of Combinatorics 12(1,N5) (2005)
Lazebnik, F., Ustimenko, V.A., Woldar, A.J.: Polarities and 2k-cycle free graphs. Discrete Math. 197/198, 503–513 (1999)
Naor, A., Verstraëte, J.: A note on bipartite graphs without 2k-cycles. Probability, Combinatorics and Computing 14(5-6), 845–849 (2005)
Pevzner, P.A., Tang, H., Tesler, G.: De novo repeat classification and fragment assembly. Genome Research 14(9), 1786–1796 (2004)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2008 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Kortsarz, G., Langberg, M., Nutov, Z. (2008). Approximating Maximum Subgraphs without Short Cycles. In: Goel, A., Jansen, K., Rolim, J.D.P., Rubinfeld, R. (eds) Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques. APPROX RANDOM 2008 2008. Lecture Notes in Computer Science, vol 5171. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-85363-3_10
Download citation
DOI: https://doi.org/10.1007/978-3-540-85363-3_10
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-85362-6
Online ISBN: 978-3-540-85363-3
eBook Packages: Computer ScienceComputer Science (R0)