## Abstract

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 language | English |
---|---|

Title of host publication | Graph-Theoretic Concepts in Computer Science - 45th International Workshop, WG 2019, Revised Papers |

Editors | Ignasi Sau, Dimitrios M. Thilikos |

Place of Publication | Cham |

Publisher | Springer |

Pages | 27-39 |

Number of pages | 13 |

ISBN (Electronic) | 978-3-030-30786-8 |

ISBN (Print) | 978-3-030-30785-1 |

DOIs | |

Publication status | Published - 12 Sep 2019 |

Event | 45th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2019 - Catalonia, Spain Duration: 19 Jun 2019 → 21 Jun 2019 |

### Publication series

Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|

Volume | 11789 LNCS |

ISSN (Print) | 0302-9743 |

ISSN (Electronic) | 1611-3349 |

### Conference

Conference | 45th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2019 |
---|---|

Country | Spain |

City | Catalonia |

Period | 19/06/19 → 21/06/19 |

## Keywords

- Fixed-parameter tractability
- Hamiltonicity
- Kernelization