On the Complexity of Determining Whether there is a Unique Hamiltonian Cycle or Path - Equipe Cybersécurité et Cryptographie Accéder directement au contenu
Article Dans Une Revue WSEAS Transactions on Mathematics Année : 2022

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

Olivier Hudry
Antoine Lobstein

Résumé

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.
Fichier principal
Vignette du fichier
OH-AL-JCMCC-unique-Ham.pdf (251.53 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-01680709 , version 1 (30-11-2020)

Identifiants

  • HAL Id : hal-01680709 , version 1

Citer

Olivier Hudry, Antoine Lobstein. On the Complexity of Determining Whether there is a Unique Hamiltonian Cycle or Path. WSEAS Transactions on Mathematics, 2022, 21, pp.433-446. ⟨hal-01680709⟩
215 Consultations
248 Téléchargements

Partager

Gmail Facebook X LinkedIn More