Document Open Access Logo

Approximating Long Cycle Above Dirac’s Guarantee

Authors Fedor V. Fomin, Petr A. Golovach, Danil Sagunov, Kirill Simonov

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2023.60.pdf
  • Filesize: 0.8 MB
  • 18 pages

Document Identifiers

Author Details

Fedor V. Fomin
  • Department of Informatics, University of Bergen, Norway
Petr A. Golovach
  • Department of Informatics, University of Bergen, Norway
Danil Sagunov
  • St. Petersburg Department of V.A. Steklov Institute of Mathematics, Russia
Kirill Simonov
  • Hasso Plattner Institute, Universität Potsdam, Germany

Funding

Supported by the Research Council of Norway via the project BWCA (grant no. 314528) and DFG Research Group ADYN via grant DFG 411362735.

Cite As Get BibTex

Fedor V. Fomin, Petr A. Golovach, Danil Sagunov, and Kirill Simonov. Approximating Long Cycle Above Dirac’s Guarantee. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 60:1-60:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023) https://doi.org/10.4230/LIPIcs.ICALP.2023.60

Abstract

Parameterization above (or below) a guarantee is a successful concept in parameterized algorithms. The idea is that many computational problems admit "natural" guarantees bringing to algorithmic questions whether a better solution (above the guarantee) could be obtained efficiently. For example, for every boolean CNF formula on m clauses, there is an assignment that satisfies at least m/2 clauses. How difficult is it to decide whether there is an assignment satisfying more than m/2 + k clauses? Or, if an n-vertex graph has a perfect matching, then its vertex cover is at least n/2. Is there a vertex cover of size at least n/2 + k for some k ≥ 1 and how difficult is it to find such a vertex cover? 
The above guarantee paradigm has led to several exciting discoveries in the areas of parameterized algorithms and kernelization. We argue that this paradigm could bring forth fresh perspectives on well-studied problems in approximation algorithms. Our example is the longest cycle problem. One of the oldest results in extremal combinatorics is the celebrated Dirac’s theorem from 1952. Dirac’s theorem provides the following guarantee on the length of the longest cycle: for every 2-connected n-vertex graph G with minimum degree δ(G) ≤ n/2, the length of the longest cycle L is at least 2δ(G). Thus the "essential" part of finding the longest cycle is in approximating the "offset" k = L - 2δ(G). The main result of this paper is the above-guarantee approximation theorem for k. Informally, the theorem says that approximating the offset k is not harder than approximating the total length L of a cycle. In other words, for any (reasonably well-behaved) function f, a polynomial time algorithm constructing a cycle of length f(L) in an undirected graph with a cycle of length L, yields a polynomial time algorithm constructing a cycle of length 2δ(G)+Ω(f(k)).

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Graph algorithms
  • Theory of computation → Approximation algorithms analysis
  • Theory of computation → Parameterized complexity and exact algorithms
Keywords
  • Longest path
  • longest cycle
  • approximation algorithms
  • above guarantee parameterization
  • minimum degree
  • Dirac theorem

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Noga Alon, Gregory Gutin, Eun Jung Kim, Stefan Szeider, and Anders Yeo. Solving MAX-r-SAT above a tight lower bound. In Proceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 511-517. SIAM, 2010. Google Scholar
  2. Noga Alon, Raphael Yuster, and Uri Zwick. Color-coding. J. ACM, 42(4):844-856, 1995. URL: https://doi.org/10.1145/210332.210337.
  3. Cristina Bazgan, Miklos Santha, and Zsolt Tuza. On the approximation of finding a(nother) hamiltonian cycle in cubic hamiltonian graphs. J. Algorithms, 31(1):249-268, 1999. URL: https://doi.org/10.1006/jagm.1998.0998.
  4. Ivona Bezáková, Radu Curticapean, Holger Dell, and Fedor V. Fomin. Finding detours is fixed-parameter tractable. SIAM J. Discrete Math., 33(4):2326-2345, 2019. URL: https://doi.org/10.1137/17M1148566.
  5. Andreas Björklund. Determinant sums for undirected hamiltonicity. SIAM J. Comput., 43(1):280-299, 2014. URL: https://doi.org/10.1137/110839229.
  6. Andreas Björklund and Thore Husfeldt. Finding a path of superlogarithmic length. SIAM J. Comput., 32(6):1395-1402, 2003. URL: https://doi.org/10.1137/S0097539702416761.
  7. Andreas Björklund, Thore Husfeldt, Petteri Kaski, and Mikko Koivisto. Narrow sieves for parameterized paths and packings. CoRR, abs/1007.1161, 2010. URL: https://arxiv.org/abs/1007.1161.
  8. Andreas Björklund, Thore Husfeldt, and Sanjeev Khanna. Approximating longest directed paths and cycles. In Proceedings of the 31st International Colloquium on Automata, Languages and Programming (ICALP), volume 3142 of Lecture Notes in Comput. Sci., pages 222-233. Springer, 2004. URL: https://doi.org/10.1007/978-3-540-27836-8_21.
  9. Hans L. Bodlaender. On linear time minor tests with depth-first search. J. Algorithms, 14(1):1-23, 1993. URL: https://doi.org/10.1006/jagm.1993.1001.
  10. B. Bollobás and A. D. Scott. Better bounds for Max Cut. In Contemporary combinatorics, volume 10 of Bolyai Soc. Math. Stud., pages 185-246. János Bolyai Math. Soc., Budapest, 2002. Google Scholar
  11. Béla Bollobás. Extremal graph theory. In Handbook of combinatorics, Vol. 1, 2, pages 1231-1292. Elsevier Sci. B. V., Amsterdam, 1995. Google Scholar
  12. J. A. Bondy. Basic graph theory: paths and circuits. In Handbook of combinatorics, Vol. 1, 2, pages 3-110. Elsevier Sci. B. V., Amsterdam, 1995. Google Scholar
  13. Guantao Chen, Zhicheng Gao, Xingxing Yu, and Wenan Zang. Approximating longest cycles in graphs with bounded degrees. SIAM Journal on Computing, 36(3):635-656, 2006. Google Scholar
  14. Robert Crowston, Mark Jones, Gabriele Muciaccia, Geevarghese Philip, Ashutosh Rai, and Saket Saurabh. Polynomial kernels for lambda-extendible properties parameterized above the Poljak-Turzik bound. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS), volume 24 of Leibniz International Proceedings in Informatics (LIPIcs), pages 43-54, Dagstuhl, Germany, 2013. Schloss Dagstuhl - Leibniz-Zentrum für Informatik. Google Scholar
  15. Marek Cygan, Fedor V. Fomin, Łukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk, and Saket Saurabh. Parameterized Algorithms. Springer, 2015. Google Scholar
  16. Reinhard Diestel. Graph theory, volume 173 of Graduate Texts in Mathematics. Springer-Verlag, Berlin, 5th edition, 2017. Google Scholar
  17. G. A. Dirac. Some theorems on abstract graphs. Proc. London Math. Soc. (3), 2:69-81, 1952. Google Scholar
  18. C. S. Edwards. Some extremal properties of bipartite subgraphs. Canad. J. Math., 3:475-485, 1973. Google Scholar
  19. P. Erdős and T. Gallai. On maximal paths and circuits of graphs. Acta Math. Acad. Sci. Hungar, 10:337-356, 1959. Google Scholar
  20. Tomás Feder and Rajeev Motwani. Finding large cycles in Hamiltonian graphs. Discrete Appl. Math., 158(8):882-893, 2010. URL: https://doi.org/10.1016/j.dam.2009.12.006.
  21. Tomás Feder, Rajeev Motwani, and Carlos Subi. Approximating the longest cycle problem in sparse graphs. SIAM J. Comput., 31(5):1596-1607, 2002. URL: https://doi.org/10.1137/S0097539701395486.
  22. Fedor V. Fomin, Petr A. Golovach, Daniel Lokshtanov, Fahad Panolan, Saket Saurabh, and Meirav Zehavi. Going far from degeneracy. SIAM J. Discrete Math., 34(3):1587-1601, 2020. URL: https://doi.org/10.1137/19M1290577.
  23. Fedor V. Fomin, Petr A. Golovach, Daniel Lokshtanov, Fahad Panolan, Saket Saurabh, and Meirav Zehavi. Multiplicative parameterization above a guarantee. ACM Trans. Comput. Theory, 13(3):18:1-18:16, 2021. URL: https://doi.org/10.1145/3460956.
  24. Fedor V. Fomin, Petr A. Golovach, Danil Sagunov, and Kirill Simonov. Algorithmic extensions of Dirac’s theorem. In Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 406-416, 2022. URL: https://doi.org/10.1137/1.9781611977073.20.
  25. Fedor V. Fomin, Petr A. Golovach, Danil Sagunov, and Kirill Simonov. Longest cycle above erdős-gallai bound. In 30th Annual European Symposium on Algorithms, ESA 2022, September 5-9, 2022, Berlin/Potsdam, Germany, volume 244 of LIPIcs, pages 55:1-55:15. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022. URL: https://doi.org/10.4230/LIPIcs.ESA.2022.55.
  26. Fedor V. Fomin, Petr A. Golovach, Danil Sagunov, and Kirill Simonov. Approximating long cycle above dirac’s guarantee. CoRR, abs/2305.02011, 2023. URL: https://arxiv.org/abs/2305.02011.
  27. Fedor V. Fomin and Petteri Kaski. Exact exponential algorithms. Commun. ACM, 56(3):80-88, 2013. URL: https://doi.org/10.1145/2428556.2428575.
  28. Fedor V. Fomin, Daniel Lokshtanov, Fahad Panolan, and Saket Saurabh. Efficient computation of representative families with applications in parameterized and exact algorithms. J. ACM, 63(4):29:1-29:60, 2016. URL: https://doi.org/10.1145/2886094.
  29. Martin Fürer and Balaji Raghavachari. Approximating the minimum-degree steiner tree to within one of optimal. J. Algorithms, 17(3):409-423, 1994. URL: https://doi.org/10.1006/jagm.1994.1042.
  30. Harold N. Gabow. Finding paths and cycles of superpolylogarithmic length. SIAM J. Comput., 36(6):1648-1671, 2007. URL: https://doi.org/10.1137/S0097539704445366.
  31. Harold N. Gabow and Shuxin Nie. Finding a long directed cycle. ACM Transactions on Algorithms, 4(1), 2008. URL: https://doi.org/10.1145/1328911.1328918.
  32. Harold N. Gabow and Shuxin Nie. Finding long paths, cycles and circuits. In Proceedings of the 19th International Symposium on Algorithms and Computation (ISAAC), volume 5369 of Lecture Notes in Comput. Sci., pages 752-763. Springer, 2008. URL: https://doi.org/10.1007/978-3-540-92182-0_66.
  33. Shivam Garg and Geevarghese Philip. Raising the bar for vertex cover: Fixed-parameter tractability above a higher guarantee. In Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1152-1166. SIAM, 2016. URL: https://doi.org/10.1137/1.9781611974331.ch80.
  34. Gregory Gutin, Eun Jung Kim, Michael Lampis, and Valia Mitsou. Vertex cover problem parameterized above and below tight bounds. Theory of Computing Systems, 48(2):402-410, 2011. URL: https://doi.org/10.1007/s00224-010-9262-y.
  35. Gregory Gutin, Leo van Iersel, Matthias Mnich, and Anders Yeo. Every ternary permutation constraint satisfaction problem parameterized above average has a kernel with a quadratic number of variables. J. Computer and System Sciences, 78(1):151-163, 2012. URL: https://doi.org/10.1016/j.jcss.2011.01.004.
  36. Gregory Z. Gutin and Matthias Mnich. A survey on graph problems parameterized above and below guaranteed values. CoRR, abs/2207.12278, 2022. URL: https://doi.org/10.48550/arXiv.2207.12278.
  37. Gregory Z. Gutin and Viresh Patel. Parameterized traveling salesman problem: Beating the average. SIAM J. Discrete Math., 30(1):220-238, 2016. Google Scholar
  38. Gregory Z. Gutin, Arash Rafiey, Stefan Szeider, and Anders Yeo. The linear arrangement problem parameterized above guaranteed value. Theory Comput. Syst., 41(3):521-538, 2007. URL: https://doi.org/10.1007/s00224-007-1330-6.
  39. Russell Impagliazzo, Ramamohan Paturi, and Francis Zane. Which problems have strongly exponential complexity. J. Computer and System Sciences, 63(4):512-530, 2001. Google Scholar
  40. Bart M. P. Jansen, László Kozma, and Jesper Nederlof. Hamiltonicity below Dirac’s condition. In Proceedings of the 45th International Workshop on Graph-Theoretic Concepts in Computer Science (WG), volume 11789 of Lecture Notes in Computer Science, pages 27-39. Springer, 2019. Google Scholar
  41. David R. Karger, Rajeev Motwani, and G. D. S. Ramkumar. On approximating the longest path in a graph. Algorithmica, 18(1):82-98, 1997. URL: https://doi.org/10.1007/BF02523689.
  42. Jon M. Kleinberg and Éva Tardos. Algorithm design. Addison-Wesley, 2006. Google Scholar
  43. Ioannis Koutis. Faster algebraic algorithms for path and packing problems. In Proceedings of the 35th International Colloquium on Automata, Languages and Programming (ICALP), volume 5125 of Lecture Notes in Comput. Sci., pages 575-586. Springer, 2008. Google Scholar
  44. Ioannis Koutis and Ryan Williams. Algebraic fingerprints for faster algorithms. Commun. ACM, 59(1):98-105, 2016. URL: https://doi.org/10.1145/2742544.
  45. Daniel Lokshtanov, N. S. Narayanaswamy, Venkatesh Raman, M. S. Ramanujan, and Saket Saurabh. Faster parameterized algorithms using linear programming. ACM Trans. Algorithms, 11(2):15:1-15:31, 2014. URL: https://doi.org/10.1145/2566616.
  46. Meena Mahajan, Venkatesh Raman, and Somnath Sikdar. Parameterizing above or below guaranteed values. J. Computer and System Sciences, 75(2):137-153, 2009. URL: https://doi.org/10.1016/j.jcss.2008.08.004.
  47. Sounaka Mishra, Venkatesh Raman, Saket Saurabh, Somnath Sikdar, and C. R. Subramanian. The complexity of König subgraph problems and above-guarantee vertex cover. Algorithmica, 61(4):857-881, 2011. URL: https://doi.org/10.1007/s00453-010-9412-2.
  48. B. Monien. How to find long paths efficiently. In Analysis and design of algorithms for combinatorial problems (Udine, 1982), volume 109 of North-Holland Math. Stud., pages 239-254. North-Holland, Amsterdam, 1985. URL: https://doi.org/10.1016/S0304-0208(08)73110-4.
  49. Sundar Vishwanathan. An approximation algorithm for finding long paths in hamiltonian graphs. J. Algorithms, 50(2):246-256, 2004. URL: https://doi.org/10.1016/S0196-6774(03)00093-2.
  50. Ryan Williams. Finding paths of length k in O^*(2^k) time. Inf. Process. Lett., 109(6):315-318, 2009. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact