Skip to Main content Skip to Navigation
Journal articles

On the Complexity of Determining Whether there is a Unique Hamiltonian Cycle or Path

Abstract : The decision problems of the existence of a Hamiltonian cycle or of a Hamiltonian path in a given graph, and of the existence of a truth assignment satisfying a given Boolean formula C, are well-known NPcomplete problems. Here we study the problems of the uniqueness of a Hamiltonian cycle or path in an undirected, directed or oriented graph, and show that they have the same complexity, up to polynomials, as the problem U-SAT of the uniqueness of an assignment satisfying C. As a consequence, these Hamiltonian problems are NP-hard and belong to the class DP, like U-SAT.
Document type :
Journal articles
Complete list of metadata

https://hal.archives-ouvertes.fr/hal-01680709
Contributor : Antoine Lobstein Connect in order to contact the contributor
Submitted on : Monday, November 30, 2020 - 3:20:31 PM
Last modification on : Friday, July 9, 2021 - 4:35:30 AM
Long-term archiving on: : Monday, March 1, 2021 - 7:28:32 PM

File

OH-AL-JCMCC-unique-Ham.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-01680709, version 1

Citation

Olivier Hudry, Antoine Lobstein. On the Complexity of Determining Whether there is a Unique Hamiltonian Cycle or Path. Journal of Combinatorial Mathematics and Combinatorial Computing, Charles Babbage Research Centre, inPress. ⟨hal-01680709⟩

Share

Metrics

Record views

285

Files downloads

166