2026-08-11T05:35:40Z https://drops.dagstuhl.de/oai

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

Longest Cycle Above Erdős-Gallai Bound Fomin, Fedor V. Golovach, Petr A. Sagunov, Danil Simonov, Kirill Longest path longest cycle fixed-parameter tractability above guarantee parameterization average degree Erdős and Gallai theorem 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. 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 244, 30th Annual European Symposium on Algorithms (ESA 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2022.55 urn:nbn:de:0030-drops-169935 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2022.55 eng https://creativecommons.org/licenses/by/4.0/legalcode