Long Cycles in Graphs: Extremal Combinatorics Meets Parameterized Algorithms
Journal article, Peer reviewed
MetadataVis full innførsel
OriginalversjonLeibniz International Proceedings in Informatics. 2022, 241, 1:1-1:4. https://doi.org/10.4230/LIPIcs.MFCS.2022.1
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.