Document Open Access Logo

Longest Cycle Above Erdős-Gallai Bound

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

PDF

File

Thumbnail PDF
PDF
LIPIcs.ESA.2022.55.pdf
  • Filesize: 0.78 MB
  • 15 pages

Document Identifiers

Related Versions

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Graph algorithms
  • Theory of computation → Parameterized complexity and exact algorithms
Keywords
  • Longest path
  • longest cycle
  • fixed-parameter tractability
  • above guarantee parameterization
  • average degree
  • Erdős and Gallai theorem

Metrics

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

Abstract

In 1959, Erdős and Gallai proved that every graph G with average vertex degree ad(G) ≥ 2 contains a cycle of length at least ad(G). We provide an algorithm that for k ≥ 0 in time 2^𝒪(k)⋅n^𝒪(1) decides whether a 2-connected n-vertex graph G contains a cycle of length at least ad(G)+k. This resolves an open problem explicitly mentioned in several papers. The main ingredients of our algorithm are new graph-theoretical results interesting on their own.

Cite As Get BibTex

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). Leibniz International Proceedings in Informatics (LIPIcs), Volume 244, pp. 55:1-55:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022) https://doi.org/10.4230/LIPIcs.ESA.2022.55

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
  • Algorithms and Complexity Group, TU Wien, Austria

Funding

  • Fomin, Fedor V.: supported by the Research Council of Norway via the project BWCA (grant no. 314528).
  • Golovach, Petr A.: supported by the Research Council of Norway via the project BWCA (grant no. 314528).
  • Sagunov, Danil: supported by Leonhard Euler International Mathematical Institute in Saint Petersburg (agreement no. 075-15-2019-1620).
  • Simonov, Kirill: supported by the Austrian Science Fund (FWF) via project Y1329 (Parameterized Analysis in Artificial Intelligence).

References

  1. Ivona Bezáková, Radu Curticapean, Holger Dell, and Fedor V. Fomin. Finding detours is fixed-parameter tractable. In 44th International Colloquium on Automata, Languages, and Programming, ICALP 2017, volume 80 of LIPIcs, pages 54:1-54:14. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2017. Google Scholar
  2. 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
  3. Gabriel A. Dirac. Some theorems on abstract graphs. Proc. London Math. Soc. (3), 2:69-81, 1952. Google Scholar
  4. Paul Erdös and Tibor Gallai. On maximal paths and circuits of graphs. Acta Math. Acad. Sci. Hungar, 10:337-356 (unbound insert), 1959. Google Scholar
  5. Genghua Fan. Long cycles and the codiameter of a graph, I. J. Comb. Theory, Ser. B, 49(2):151-180, 1990. URL: https://doi.org/10.1016/0095-8956(90)90024-T.
  6. Fedor V. Fomin, Petr A. Golovach, Daniel Lokshtanov, Fahad Panolan, Saket Saurabh, and Meirav Zehavi. Going far from degeneracy. SIAM J. Discret. Math., 34(3):1587-1601, 2020. URL: https://doi.org/10.1137/19M1290577.
  7. Fedor V. Fomin, Petr A. Golovach, Daniel Lokshtanov, Fahad Panolan, Saket Saurabh, and Meirav Zehavi. Parameterization above a multiplicative guarantee. In 11th Innovations in Theoretical Computer Science Conference (ITCS), volume 151 of LIPIcs, pages 39:1-39:13. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. URL: https://doi.org/10.4230/LIPIcs.ITCS.2020.39.
  8. Fedor V. Fomin, Petr A. Golovach, Danil Sagunov, and Kirill Simonov. Algorithmic extensions of Dirac’s theorem. CoRR, abs/2011.03619, 2020. URL: http://arxiv.org/abs/2011.03619.
  9. Fedor V. Fomin, Petr A. Golovach, Danil Sagunov, and Kirill Simonov. Algorithmic extensions of Dirac’s theorem. In Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, (SODA 2022), pages 931-950. SIAM, 2022. URL: https://doi.org/10.1137/1.9781611977073.20.
  10. Fedor V. Fomin, Petr A. Golovach, Danil Sagunov, and Kirill Simonov. Longest cycle above Erdős-Gallai bound. CoRR, abs/2202.03061, 2022. URL: http://arxiv.org/abs/2202.03061.
  11. Fedor V. Fomin, Daniel Lokshtanov, Fahad Panolan, Saket Saurabh, and Meirav Zehavi. Long directed (s,t)-path: FPT algorithm. Inf. Process. Lett., 140:8-12, 2018. URL: https://doi.org/10.1016/j.ipl.2018.04.018.
  12. Giorgio Gallo, Michael D. Grigoriadis, and Robert Endre Tarjan. A fast parametric maximum flow algorithm and applications. SIAM J. Comput., 18(1):30-55, 1989. URL: https://doi.org/10.1137/0218003.
  13. Andrew V. Goldberg. Finding a maximum density subgraph. Technical Report CSD-84-171, University of California, 1984. Google Scholar
  14. Russell Impagliazzo, Ramamohan Paturi, and Francis Zane. Which problems have strongly exponential complexity? J. Comput. Syst. Sci., 63(4):512-530, 2001. URL: https://doi.org/10.1006/jcss.2001.1774.
  15. 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
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-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact