  In 1952, Dirac proved the following theorem about long cycles in graphs with
large minimum vertex degrees: Every $n$-vertex $2$-connected graph $G$ with
minimum vertex degree $\delta\geq 2$ contains a cycle with at least
$\min\{2\delta,n\}$ vertices. In particular, if $\delta\geq n/2$, then $G$ is
Hamiltonian. The proof of Dirac's theorem is constructive, and it yields an
algorithm computing the corresponding cycle in polynomial time. The
combinatorial bound of Dirac's theorem is tight in the following sense. There
are 2-connected graphs that do not contain cycles of length more than
$2\delta+1$. Also, there are non-Hamiltonian graphs with all vertices but one
of degree at least $n/2$. This prompts naturally to the following algorithmic
questions. For $k\geq 1$,
  (A) How difficult is to decide whether a 2-connected graph contains a cycle
of length at least $\min\{2\delta+k,n\}$?
  (B) How difficult is to decide whether a graph $G$ is Hamiltonian, when at
least $n - k$ vertices of $G$ are of degrees at least $n/2-k$?
  The first question was asked by Fomin, Golovach, Lokshtanov, Panolan,
Saurabh, and Zehavi. The second question is due to Jansen, Kozma, and Nederlof.
Even for a very special case of $k=1$, the existence of a polynomial-time
algorithm deciding whether $G$ contains a cycle of length at least
$\min\{2\delta+1,n\}$ was open. We resolve both questions by proving the
following algorithmic generalization of Dirac's theorem: If all but $k$
vertices of a $2$-connected graph $G$ are of degree at least $\delta$, then
deciding whether $G$ has a cycle of length at least $\min\{2\delta +k, n\}$ can
be done in time $2^{\mathcal{O}(k)}\cdot n^{\mathcal{O}(1)}$.
  The proof of the algorithmic generalization of Dirac's theorem builds on new
graph-theoretical results that are interesting on their own.
