On the Complexity of Determining Whether there is a Unique Hamiltonian Cycle or Path
Journal of Combinatorial Mathematics and Combinatorial Computing, à paraître.
Olivier HUDRY (#) & Antoine LOBSTEIN (*)
MALHEUREUSEMENT, CETTE REVUE A CESSÉ DE PARAÎTRE ;
UNFORTUNATELY, THIS JOURNAL HAS CEASED TO BE PUBLISHED ...
EN CONSÉQUENCE, nous avons dû changer notre fusil d'épaule,
THEREFORE, we changed our tactics,
MAIS LE PROCESSUS A ÉTÉ TRÈS LONG !
BUT THIS TOOK US A LOT OF TIME!
On the Complexity of Determining Whether there is a Unique Hamiltonian Cycle or Path
WSEAS (World Scientific and Engineering Academy and Society)
Transactions on Mathematics, Vol. 21, pp. 433-446, 2022.
Olivier HUDRY (#) & Antoine LOBSTEIN (*)
(#) Département Informatique et Réseaux, LTCI,
Télécom ParisTech, Université Paris-Saclay,
46 rue Barrault, 75634 Paris Cedex 13 - France
olivier.hudry@telecom-paristech.fr
(*) Centre National de la Recherche Scientifique,
Laboratoire de Recherche en Informatique, UMR 8623,
Université Paris-Sud, Université Paris-Saclay,
Bâtiment 650 Ada Lovelace, 91405 Orsay Cedex - France
antoine.lobstein@lri.fr
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 NP-complete 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.
