2026-08-10T23:32:03Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:16799 2024-03-06T10:58:21Z ddc:004 open_access

Long Cycles in Graphs: Extremal Combinatorics Meets Parameterized Algorithms (Invited Talk) Fomin, Fedor V. Golovach, Petr A. Sagunov, Danil Simonov, Kirill Longest path longest cycle fixed-parameter tractability above guarantee parameterization average degree dense graph Dirac theorem Erdős-Gallai theorem 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Fedor V. Fomin and Petr A. Golovach and Danil Sagunov and Kirill Simonov 2022 Is Part Of LIPIcs, Volume 241, 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2022.1 urn:nbn:de:0030-drops-167999 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2022.1 eng https://creativecommons.org/licenses/by/4.0/legalcode