论文标题
关于确定是否存在独特的哈密顿周期还是路径的复杂性
On the Complexity of Determining Whether there is a Unique Hamiltonian Cycle or Path
论文作者
论文摘要
在给定图中存在哈密顿周期或哈密顿路径的决策问题，以及满足给定的布尔公式$ c $的真相分配的存在是众所周知的{\ it np} - complete问题。在这里，我们研究了无方向性，有向或定向图中哈密顿周期或路径的{\ it唯一性}的问题，并表明它们具有相同的复杂性，直到多项式为多项式，因为问题的usat u-sat的唯一性是满足$ c $ c $的任务。结果，这些哈密顿问题是{\ it np} -hard，属于〜{\ it dp}类，就像u-sat一样。
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 {\it NP}-complete problems. Here we study the problems of the {\it 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 {\it NP}-hard and belong to the class~{\it DP}, like U-SAT.
