- This event has passed.
Fedor Fomin, Long cycles in graphs: Extremal Combinatorics meets Parameterized Algorithms
Thursday, March 10, 2022 @ 4:30 PM - 5:30 PM KST
We examine algorithmic extensions of two classic results of extremal combinatorics. 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 2-connected graph G with the average vertex degree D>1, contains a cycle of length at least D.
We discuss the recent progress in parameterized complexity of computing long cycles “above” the guarantees established by these classical theorems: cycles of lengths at least 2d+k and D+k.
The talk is based on the joint works with Petr Golovach, Danil Sagunov, and Kirill Simonov.