LIPIcs.MFCS.2022.1.pdf
- Filesize: 0.57 MB
- 4 pages
Document
Long Cycles in Graphs: Extremal Combinatorics Meets Parameterized Algorithms (Invited Talk)
Authors
Fedor V. Fomin 
,
Petr A. Golovach ,
Danil Sagunov ,
Kirill Simonov
-
Part of:
Volume:
47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: Mathematical Foundations of Computer Science (MFCS) - License:
Creative Commons Attribution 4.0 International license
- Publication Date: 2022-08-22
File
Document Identifiers
Author Details
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
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.
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)
0PDF Downloads
References
-
Marek Cygan, Fedor V. Fomin, Łukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk, and Saket Saurabh. Parameterized Algorithms. Springer, 2015.
-
Gabriel Andrew Dirac. Some theorems on abstract graphs. Proc. London Math. Soc. (3), 2:69-81, 1952.
-
Paul Erdős and Tibor Gallai. On maximal paths and circuits of graphs. Acta Math. Acad. Sci. Hungar, 10:337-356 (unbound insert), 1959.
- 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.
- 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.
- 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.