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

Olivier Hudry; Antoine Lobstein

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

Olivier Hudry
, Antoine Lobstein

Research output: Contribution to journal › Article › peer-review

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 ori-ented 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-haid and belong to the class DP, like U-SAT.

Original language	English
Pages (from-to)	85-106
Number of pages	22
Journal	Journal of Combinatorial Mathematics and Combinatorial Computing
Volume	111
Publication status	Published - 1 Nov 2019
Externally published	Yes

Keywords

Boolean Satisfiability Problems
Complexity Theory
Decision Problems
Graph Theory
Hamiltonian Cycle
Hamiltonian Path
NP-Hardness
Polynomial Reduction
Travelling Salesman
Uniqueness of Solution

Cite this

@article{9fa07c775e5b4b708e52107c74331dce,

title = "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 NP-complete problems. Here we study the problems of the uniqueness of a Hamiltonian cycle or path in an undirected, directed or ori-ented 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-haid and belong to the class DP, like U-SAT.",

keywords = "Boolean Satisfiability Problems, Complexity Theory, Decision Problems, Graph Theory, Hamiltonian Cycle, Hamiltonian Path, NP-Hardness, Polynomial Reduction, Travelling Salesman, Uniqueness of Solution",

author = "Olivier Hudry and Antoine Lobstein",

year = "2019",

month = nov,

day = "1",

language = "English",

volume = "111",

pages = "85--106",

journal = "Journal of Combinatorial Mathematics and Combinatorial Computing",

issn = "0835-3026",

}

TY - JOUR

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

AU - Hudry, Olivier

AU - Lobstein, Antoine

PY - 2019/11/1

Y1 - 2019/11/1

N2 - 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 ori-ented 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-haid and belong to the class DP, like U-SAT.

AB - 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 ori-ented 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-haid and belong to the class DP, like U-SAT.

KW - Boolean Satisfiability Problems

KW - Complexity Theory

KW - Decision Problems

KW - Graph Theory

KW - Hamiltonian Cycle

KW - Hamiltonian Path

KW - NP-Hardness

KW - Polynomial Reduction

KW - Travelling Salesman

KW - Uniqueness of Solution

UR - https://www.scopus.com/pages/publications/85096363339

M3 - Article

AN - SCOPUS:85096363339

SN - 0835-3026

VL - 111

SP - 85

EP - 106

JO - Journal of Combinatorial Mathematics and Combinatorial Computing

JF - Journal of Combinatorial Mathematics and Combinatorial Computing

ER -

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

Abstract

Keywords

Other files and links

Fingerprint

Cite this