HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
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 : Monday, January 24, 2022 - 11:43:20 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

150

Files downloads

118