Hamiltonicity below Dirac’s condition

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademicpeer review

1 Citaat (Scopus)

Samenvatting

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.

Originele taal-2Engels
TitelGraph-Theoretic Concepts in Computer Science - 45th International Workshop, WG 2019, Revised Papers
RedacteurenIgnasi Sau, Dimitrios M. Thilikos
Plaats van productieCham
UitgeverijSpringer
Pagina's27-39
Aantal pagina's13
ISBN van elektronische versie978-3-030-30786-8
ISBN van geprinte versie978-3-030-30785-1
DOI's
StatusGepubliceerd - 12 sep 2019
Evenement45th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2019 - Catalonia, Spanje
Duur: 19 jun 201921 jun 2019

Publicatie series

NaamLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume11789 LNCS
ISSN van geprinte versie0302-9743
ISSN van elektronische versie1611-3349

Congres

Congres45th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2019
LandSpanje
StadCatalonia
Periode19/06/1921/06/19

Vingerafdruk Duik in de onderzoeksthema's van 'Hamiltonicity below Dirac’s condition'. Samen vormen ze een unieke vingerafdruk.

  • Citeer dit

    Jansen, B. M. P., Kozma, L., & Nederlof, J. (2019). Hamiltonicity below Dirac’s condition. In I. Sau, & D. M. Thilikos (editors), Graph-Theoretic Concepts in Computer Science - 45th International Workshop, WG 2019, Revised Papers (blz. 27-39). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 11789 LNCS). Springer. https://doi.org/10.1007/978-3-030-30786-8_3