WSEAS Transactions on Mathematics
Print ISSN: 1109-2769, E-ISSN: 2224-2880
Volume 21, 2022
On the Complexity of Determining Whether there is a Unique Hamiltonian Cycle or Path
Authors: ,
Abstract: The decision problems of the existence of a Hamiltonian cycle or of a Hamiltonian path in a given directed or undirected 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.
Search Articles
Keywords: Graph Theory, Hamiltonian Cycle, Hamiltonian Path, Complexity Theory, NP-Hardness, class DP, Decision Problems, Polynomial Reduction, Uniqueness of Solution, Boolean Satisfiability Problems
Pages: 433-446
DOI: 10.37394/23206.2022.21.51