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.
| Original language | English |
|---|---|
| Pages (from-to) | 433-446 |
| Number of pages | 14 |
| Journal | WSEAS Transactions on Mathematics |
| Volume | 21 |
| DOIs | |
| Publication status | Published - 1 Jan 2022 |
UN SDGs
This output contributes to the following UN Sustainable Development Goals (SDGs)
-
SDG 3 Good Health and Well-being
Keywords
- Boolean Satisfiability Problems
- Complexity Theory
- Decision Problems
- Graph Theory
- Hamiltonian Cycle
- Hamiltonian Path
- NP-Hardness
- Polynomial Reduction
- Uniqueness of Solution
- class DP
Fingerprint
Dive into the research topics of 'On the Complexity of Determining Whether there is a Unique Hamiltonian Cycle or Path'. Together they form a unique fingerprint.Cite this
- APA
- Author
- BIBTEX
- Harvard
- Standard
- RIS
- Vancouver