Randomized Reductions and the Topology of Conjectured Classes of Uniquely Hamiltonian Graphs
-
- Barish Robert D.
- Graduate School of Arts and Sciences, The University of Tokyo
-
- Suyama Akira
- Graduate School of Arts and Sciences, The University of Tokyo
Abstract
<p>We utilize the hardness of the Unambiguous-SAT problem under randomized polynomial time reductions (Valiant & Vazirani; Theoret. Comput. Sci., Vol.47, 1986) to probe the required properties of counterexamples to open non-existence conjectures for uniquely Hamiltonian graphs under various topological constraints. Concerning ourselves with a generalization of Sheehan's 1975 conjecture that no uniquely Hamiltonian graphs exist in the class of (r ∈ 2 ℕ>1)-regular graphs (for 4 ≤ r ≤ 22), Bondy & Jackson's 1998 conjecture that no uniquely Hamiltonian graphs exist in the class of planar graphs having at most one vertex of degree ≤ 2, and Fleischner's 2014 conjecture that no uniquely Hamiltonian graphs exist in the class of 4-vertex-connected graphs, we prove that each conjecture is false if and only if there exists a parsimonious reduction from #SAT to counting Hamiltonian cycles on each graph class in question. As the existence of such a reduction allows for the encoding of arbitrary Unambiguous-SAT problem instances, by the Valiant-Vazirani theorem we have that hypothetical sets of counterexamples for each non-existence conjecture cannot belong to any graph class with a polynomial time testable property implying tractability for the Hamiltonian cycle decision problem (unless NP = RP).</p>
Journal
-
- Journal of Information Processing
-
Journal of Information Processing 28 (0), 876-888, 2020
Information Processing Society of Japan
- Tweet
Keywords
Details 詳細情報について
-
- CRID
- 1391131406290029568
-
- NII Article ID
- 130007956341
-
- ISSN
- 18826652
-
- Text Lang
- en
-
- Data Source
-
- JaLC
- Crossref
- CiNii Articles
-
- Abstract License Flag
- Disallowed