---
_id: '12432'
abstract:
- lang: eng
  text: "We present CertifyHAM, a deterministic algorithm that takes a graph G as
    input and either finds a Hamilton cycle of G or outputs that such a cycle does
    not exist. If G ∼ G(n, p) and p ≥\r\n100 log n/n then the expected running time
    of CertifyHAM is O(n/p) which is best possible. This improves upon previous results
    due to Gurevich and Shelah, Thomason and Alon, and\r\nKrivelevich, who proved
    analogous results for p being constant, p ≥ 12n −1/3 and p ≥ 70n\r\n−1/2 respectively."
acknowledgement: "This project has received funding from the European Union’s Horizon
  2020\r\nresearch and innovation programme under the Marie Skłodowska-Curie grant\r\nagreement
  No 101034413"
article_processing_charge: No
author:
- first_name: Michael
  full_name: Anastos, Michael
  id: 0b2a4358-bb35-11ec-b7b9-e3279b593dbb
  last_name: Anastos
citation:
  ama: 'Anastos M. Solving the Hamilton cycle problem fast on average. In: <i>63rd
    Annual IEEE Symposium on Foundations of Computer Science</i>. Vol 2022-October.
    Institute of Electrical and Electronics Engineers; 2022:919-930. doi:<a href="https://doi.org/10.1109/FOCS54457.2022.00091">10.1109/FOCS54457.2022.00091</a>'
  apa: 'Anastos, M. (2022). Solving the Hamilton cycle problem fast on average. In
    <i>63rd Annual IEEE Symposium on Foundations of Computer Science</i> (Vol. 2022–October,
    pp. 919–930). Denver, CO, United States: Institute of Electrical and Electronics
    Engineers. <a href="https://doi.org/10.1109/FOCS54457.2022.00091">https://doi.org/10.1109/FOCS54457.2022.00091</a>'
  chicago: Anastos, Michael. “Solving the Hamilton Cycle Problem Fast on Average.”
    In <i>63rd Annual IEEE Symposium on Foundations of Computer Science</i>, 2022–October:919–30.
    Institute of Electrical and Electronics Engineers, 2022. <a href="https://doi.org/10.1109/FOCS54457.2022.00091">https://doi.org/10.1109/FOCS54457.2022.00091</a>.
  ieee: M. Anastos, “Solving the Hamilton cycle problem fast on average,” in <i>63rd
    Annual IEEE Symposium on Foundations of Computer Science</i>, Denver, CO, United
    States, 2022, vol. 2022–October, pp. 919–930.
  ista: 'Anastos M. 2022. Solving the Hamilton cycle problem fast on average. 63rd
    Annual IEEE Symposium on Foundations of Computer Science. FOCS: Symposium on Foundations
    of Computer Science vol. 2022–October, 919–930.'
  mla: Anastos, Michael. “Solving the Hamilton Cycle Problem Fast on Average.” <i>63rd
    Annual IEEE Symposium on Foundations of Computer Science</i>, vol. 2022–October,
    Institute of Electrical and Electronics Engineers, 2022, pp. 919–30, doi:<a href="https://doi.org/10.1109/FOCS54457.2022.00091">10.1109/FOCS54457.2022.00091</a>.
  short: M. Anastos, in:, 63rd Annual IEEE Symposium on Foundations of Computer Science,
    Institute of Electrical and Electronics Engineers, 2022, pp. 919–930.
conference:
  end_date: 2022-11-03
  location: Denver, CO, United States
  name: 'FOCS: Symposium on Foundations of Computer Science'
  start_date: 2022-10-31
date_created: 2023-01-29T23:00:59Z
date_published: 2022-12-01T00:00:00Z
date_updated: 2023-08-04T09:37:56Z
day: '01'
department:
- _id: MaKw
doi: 10.1109/FOCS54457.2022.00091
ec_funded: 1
external_id:
  isi:
  - '000909382900084'
isi: 1
language:
- iso: eng
month: '12'
oa_version: None
page: 919-930
project:
- _id: fc2ed2f7-9c52-11eb-aca3-c01059dda49c
  call_identifier: H2020
  grant_number: '101034413'
  name: 'IST-BRIDGE: International postdoctoral program'
publication: 63rd Annual IEEE Symposium on Foundations of Computer Science
publication_identifier:
  isbn:
  - '9781665455190'
  issn:
  - 0272-5428
publication_status: published
publisher: Institute of Electrical and Electronics Engineers
quality_controlled: '1'
scopus_import: '1'
status: public
title: Solving the Hamilton cycle problem fast on average
type: conference
user_id: 4359f0d1-fa6c-11eb-b949-802e58b17ae8
volume: 2022-October
year: '2022'
...