Paths and Cycles Above Combinatorial Bounds

An undirected graph G d-degenerate if every subgraph of G has a vertex of degree at most d, and the degeneracy is the minimum d such that G is d-degenerate. By the classical theorem of Erdös and Gallai from 1959, every graph of degeneracy d>1 contains a cycle of length at least d+1. The proof of Erdös and Gallai is constructive and can be turned into a polynomial time algorithm constructing a cycle of length at least d+1. But can we decide in polynomial time whether a graph contains a cycle of length at least d+2? An easy reduction from Hamiltonian Cycle provides a negative answer to this question: Deciding whether a graph has a cycle of length at least d+2 is NP-complete.  Surprisingly, the complexity of the problem changes drastically when the input graph is 2-connected.  In this case we prove that    deciding whether G contains a cycle of length at least d+k can be done in time 2^{O(k)}|V(G)|^{O(1)}.  Further, we briefly consider similar problem arising from the classical result of Dirac from 1952 that every 2-connected n-vertex graph has a cycle with at least min{2\delta(G),n} vertices. 

The talk is based on the joint work with Fedor V. Fomin, Daniel Lokshtanov, Fahad Panolan, Saket Saurabh, Meirav Zehavi, Danil Sagunov, and Kirill Simonov.

We are looking forward to meeting at the video-conference. Join Zoom Meeting HERE!

Everyone is welcome and encouraged to attend.

For more info visit our YouTube Channel.