Hamiltonicity below Dirac’s condition

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

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

11 Citations (Scopus)


Dirac’s theorem (1952) is a classical result of graph theory, stating that an n-vertex graph (n≥3n≥3) 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 ck⋅nO(1)ck⋅nO(1), for a fixed constant c, if at least n−kn−k vertices have degree at least n/2, or if all vertices have degree at least n/2−kn/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.

Original languageEnglish
Title of host publicationGraph-Theoretic Concepts in Computer Science - 45th International Workshop, WG 2019, Revised Papers
EditorsIgnasi Sau, Dimitrios M. Thilikos
Place of PublicationCham
Number of pages13
ISBN (Electronic)978-3-030-30786-8
ISBN (Print)978-3-030-30785-1
Publication statusPublished - 12 Sept 2019
Event45th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2019 - Catalonia, Spain
Duration: 19 Jun 201921 Jun 2019

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume11789 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference45th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2019


  • Fixed-parameter tractability
  • Hamiltonicity
  • Kernelization


Dive into the research topics of 'Hamiltonicity below Dirac’s condition'. Together they form a unique fingerprint.

Cite this