Document Open Access Logo

Long Cycles in Graphs: Extremal Combinatorics Meets Parameterized Algorithms (Invited Talk)

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

PDF

File

Thumbnail PDF
PDF
LIPIcs.MFCS.2022.1.pdf
  • Filesize: 0.57 MB
  • 4 pages

Document Identifiers

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
  • dense graph
  • Dirac theorem
  • Erdős-Gallai theorem

Metrics

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

Abstract

We discuss recent algorithmic extensions of two classic results of extremal combinatorics about long paths in graphs. First, the theorem of Dirac from 1952 asserts that a 2-connected graph G with the minimum vertex degree d > 1, is either Hamiltonian or contains a cycle of length at least 2d. Second, the theorem of Erdős-Gallai from 1959, states that a graph G with the average vertex degree D > 1, contains a cycle of length at least D. The proofs of these theorems are constructive, they provide polynomial-time algorithms constructing cycles of lengths 2d and D. We extend these algorithmic results by showing that each of the problems, to decide whether a 2-connected graph contains a cycle of length at least 2d+k or of a cycle of length at least D+k, is fixed-parameter tractable parameterized by k.

Cite As Get BibTex

Fedor V. Fomin, Petr A. Golovach, Danil Sagunov, and Kirill Simonov. Long Cycles in Graphs: Extremal Combinatorics Meets Parameterized Algorithms (Invited Talk). In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 241, pp. 1:1-1:4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022) https://doi.org/10.4230/LIPIcs.MFCS.2022.1

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, Vienna, Austria

Funding

  • Fomin, Fedor V.: The research received funding from the Research Council of Norway via the project BWCA (grant no. 314528).
  • Sagunov, Danil: This project was supported by Leonhard Euler International Mathematical Institute in Saint Petersburg (agreement no. 075–15–2019–1620).

References

  1. 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
  2. Gabriel Andrew Dirac. Some theorems on abstract graphs. Proc. London Math. Soc. (3), 2:69-81, 1952. Google Scholar
  3. 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
  4. 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.
  5. 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.
  6. 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.
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

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