Hamiltonicity below Dirac's condition

DOI10.1007/978-3-030-30786-8_3arXiv1902.01745MaRDI QIDQ6313629FDOQ6313629

Authors: Bart M. P. Jansen, László Kozma, Jesper Nederlof 

Publication date: 5 February 2019

Abstract: Dirac's theorem (1952) is a classical result of graph theory, stating that an $n$-vertex graph ($ngeq3$) is Hamiltonian if every vertex has degree at least $n/2$. Both the value $n/2$ and the requirement for every vertex to have high degree are necessary for the theorem to hold. In this work we give efficient algorithms for determining Hamiltonicity when either of the two conditions are relaxed. More precisely, we show that the Hamiltonian cycle problem can be solved in time $c^{k}cdot{n}^{O(1)}$, for some fixed constant $c$, if at least $n-k$ vertices have degree at least $n/2$, or if all vertices have degree at least $n/2-k$. The running time is, in both cases, asymptotically optimal, under the exponential-time hypothesis (ETH). The results extend the range of tractability of the Hamiltonian cycle problem, showing that it is fixed-parameter tractable when parameterized below a natural bound. In addition, for the first parameterization we show that a kernel with $O(k)$ vertices can be found in polynomial time.

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Analysis of algorithms (68W40) Eulerian and Hamiltonian graphs (05C45) Parameterized complexity, tractability and kernelization (68Q27)

This page was built for publication: Hamiltonicity below Dirac's condition

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6313629)