$\displaystyle\min_{\beta,\beta_{0}}\left(1-\beta^{\top}H{b}\right)^{2}\sigma^{2}+\left(\left(1-\beta^{\top}H{b}\right)a^{\text{\scriptsize$(1)$}}_{Y}-\beta^{\top}Ha^{\text{\scriptsize$(1)$}}_{X}-\beta_{0}\right)^{2}+\beta^{\top}H\Sigma
H^{\top}\beta$ $\displaystyle\text{s.t.
}\beta^{\top}H\left(a^{\text{\scriptsize$(1)$}}_{X}-\widetilde{a}\right)=0$
$\displaystyle\text{and }1-\beta^{\top}H{b}=0.$ (110)

In fact, the above optimization problem is exactly the same as RIIRMI in
Equation (D.1). Consequently, the CIRMI solution is the same as that of
RIIRMI.

$\displaystyle\beta_{\text{CIRMI}}^{\text{\scriptsize$(1)$}}$
$\displaystyle=\beta_{\text{RIIRMI}}^{\text{\scriptsize$(1)$}}$ (111)
$\displaystyle\beta_{\text{CIRMI},0}^{\text{\scriptsize$(1)$}}$
$\displaystyle=\beta_{\text{RIIRMI},0}^{\text{\scriptsize$(1)$}},$
$\displaystyle\tilde{R}(f_{\text{CIRMI}}^{\text{\scriptsize$(1)$}})=\tilde{R}(f_{\text{RIIRMI}}^{\text{\scriptsize$(1)$}}).$

###  D.2 Proof of Corollary 10

The proof of Corollary 10 follows similarly as that of Corollary 6 in Appendix
C.2.

## References

  * Amini and Gallinari (2003) M Amini and Patrick Gallinari.  Semi-supervised learning with an explicit label-error model for misclassified data.  In _Proceedings of the 18th International Joint Conferences on Artificial Intelligence_ , pages 555–560, 2003.
  * Arjovsky et al. (2019) Martin Arjovsky, Léon Bottou, Ishaan Gulrajani, and David Lopez-Paz.  Invariant risk minimization.  _arXiv preprint arXiv:1907.02893_ , 2019.
  * Azizzadenesheli et al. (2019) Kamyar Azizzadenesheli, Anqi Liu, Fanny Yang, and Animashree Anandkumar.  Regularized learning for domain adaptation under label shifts.  In _International Conference on Learning Representations (ICLR)_ , 2019.
  * Baktashmotlagh et al. (2013) Mahsa Baktashmotlagh, Mehrtash T Harandi, Brian C Lovell, and Mathieu Salzmann.  Unsupervised domain adaptation by domain invariant projection.  In _Proceedings of the IEEE International Conference on Computer Vision_ , pages 769–776, 2013.
  * Ben-David et al. (2007) Shai Ben-David, John Blitzer, Koby Crammer, and Fernando Pereira.  Analysis of representations for domain adaptation.  In _Advances in Neural Information Processing Systems_ , pages 137–144, 2007.
  * Ben-David et al. (2010) Shai Ben-David, Tyler Lu, Teresa Luu, and Dávid Pál.  Impossibility theorems for domain adaptation.  In _International Conference on Artificial Intelligence and Statistics_ , pages 129–136, 2010.
  * Blitzer et al. (2011) John Blitzer, Sham Kakade, and Dean Foster.  Domain adaptation with coupled subspaces.  In _Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics_ , pages 173–181. JMLR Workshop and Conference Proceedings, 2011.
  * Blum and Mitchell (1998) Avrim Blum and Tom Mitchell.  Combining labeled and unlabeled data with co-training.  In _Proceedings of the 11th Annual Conference on Computational Learning Theory_ , pages 92–100, 1998.
  * Bühlmann (2020) Peter Bühlmann.  Invariance, causality and robustness.  _Statistical Science_ , 35(3):404–426, 2020.
  * Carmon et al. (2019) Yair Carmon, Aditi Raghunathan, Ludwig Schmidt, John C Duchi, and Percy S Liang.  Unlabeled data improves adversarial robustness.  In _Advances in Neural Information Processing Systems_ , pages 11190–11201, 2019.
  * Chapelle et al. (2009) Olivier Chapelle, Bernhard Schölkopf, and Alexander Zien.  Semi-supervised learning.  _IEEE Transactions on Neural Networks_ , 20(3):542–542, 2009.
  * Cortes and Mohri (2011) Corinna Cortes and Mehryar Mohri.  Domain adaptation in regression.  In _International Conference on Algorithmic Learning Theory_ , pages 308–323. Springer, 2011.
  * Cortes and Mohri (2014) Corinna Cortes and Mehryar Mohri.  Domain adaptation and sample bias correction theory and algorithm for regression.  _Theoretical Computer Science_ , 519:103–126, 2014.
  * Cortes et al. (2015) Corinna Cortes, Mehryar Mohri, and Andrés Muñoz Medina.  Adaptation algorithm and theory based on generalized discrepancy.  In _Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining_ , pages 169–178, 2015.
  * Duchi and Namkoong (2018) John Duchi and Hongseok Namkoong.  Learning models with uniform performance via distributionally robust optimization.  _arXiv preprint arXiv:1810.08750_ , 2018.
  * Eberhardt and Scheines (2007) Frederick Eberhardt and Richard Scheines.  Interventions and causal inference.  _Philosophy of Science_ , 74(5):981–995, 2007\.
  * Fei-Fei (2010) Li Fei-Fei.  Imagenet: crowdsourcing, benchmarking & other cool things.  In _CMU VASC Seminar_ , volume 16, pages 18–25, 2010.
  * Ganin et al. (2016) Yaroslav Ganin, Evgeniya Ustinova, Hana Ajakan, Pascal Germain, Hugo Larochelle, François Laviolette, Mario Marchand, and Victor Lempitsky.  Domain-adversarial training of neural networks.  _Journal of Machine Learning Research_ , 17(1):2096–2030, 2016.
  * Gao et al. (2017) Rui Gao, Xi Chen, and Anton J Kleywegt.  Wasserstein distributional robustness and regularization in statistical learning.  _arXiv preprint arXiv:1712.06050_ , 2017.
  * Garg et al. (2020) Saurabh Garg, Yifan Wu, Sivaraman Balakrishnan, and Zachary Lipton.  A unified view of label shift estimation.  In _Advances in Neural Information Processing Systems_ , volume 33, pages 3290–3300. Curran Associates, Inc., 2020.
  * Ghifary et al. (2016) Muhammad Ghifary, David Balduzzi, W Bastiaan Kleijn, and Mengjie Zhang.  Scatter component analysis: A unified framework for domain adaptation and domain generalization.  _IEEE Transactions on Pattern Analysis and Machine Intelligence_ , 39(7):1414–1430, 2016.
  * Glymour et al. (2019) Clark Glymour, Kun Zhang, and Peter Spirtes.  Review of causal discovery methods based on graphical models.  _Frontiers in Genetics_ , 10:524, 2019.
  * Gong et al. (2012) Boqing Gong, Yuan Shi, Fei Sha, and Kristen Grauman.  Geodesic flow kernel for unsupervised domain adaptation.  In _2012 IEEE Conference on Computer Vision and Pattern Recognition_ , pages 2066–2073. IEEE, 2012.
  * Gong et al. (2016) Mingming Gong, Kun Zhang, Tongliang Liu, Dacheng Tao, Clark Glymour, and Bernhard Schölkopf.  Domain adaptation with conditional transferable components.  In _International Conference on Machine Learning_ , pages 2839–2848, 2016.
  * Goodfellow et al. (2018) Ian Goodfellow, Patrick McDaniel, and Nicolas Papernot.  Making machine learning robust against adversarial inputs.  _Communications of the ACM_ , 61(7):56–66, 2018\.
  * Gopalan et al. (2011) Raghuraman Gopalan, Ruonan Li, and Rama Chellappa.  Domain adaptation for object recognition: An unsupervised approach.  In _2011 International Conference on Computer Vision_ , pages 999–1006. IEEE, 2011.
  * Greenfeld and Shalit (2020) Daniel Greenfeld and Uri Shalit.  Robust learning with the Hilbert-Schmidt independence criterionilbert-schmidt independence criterion.  In _International Conference on Machine Learning_ , pages 3759–3768. PMLR, 2020.
  * Gretton et al. (2012) Arthur Gretton, Karsten M Borgwardt, Malte J Rasch, Bernhard Schölkopf, and Alexander Smola.  A kernel two-sample test.  _Journal of Machine Learning Research_ , 13(Mar):723–773, 2012.
  * Heinze-Deml and Meinshausen (2021) Christina Heinze-Deml and Nicolai Meinshausen.  Conditional variance penalties and domain shift robustness.  _Machine Learning_ , 110(2):303–348, 2021.
  * Hoffman et al. (2018) Judy Hoffman, Mehryar Mohri, and Ningshan Zhang.  Algorithms and theory for multiple-source adaptation.  In _Advances in Neural Information Processing Systems_ , pages 8246–8256, 2018.
  * Huber (1964) Peter J Huber.  Robust estimation of a location parameter.  _Annals of Mathematical Statistics_ , pages 73–101, 1964.
  * Johansson et al. (2019) Fredrik D Johansson, David Sontag, and Rajesh Ranganath.  Support and invertibility in domain-invariant representations.  In _The 22nd International Conference on Artificial Intelligence and Statistics_ , pages 527–536. PMLR, 2019.
  * Kumar et al. (2020) Ananya Kumar, Tengyu Ma, and Percy Liang.  Understanding self-training for gradual domain adaptation.  In _International Conference on Machine Learning_ , pages 5468–5479. PMLR, 2020.
  * Laurent and Massart (2000) Beatrice Laurent and Pascal Massart.  Adaptive estimation of a quadratic functional by model selection.  _Annals of Statistics_ , pages 1302–1338, 2000.
  * LeCun (1998) Yann LeCun.  The MNIST database of handwritten digits.  _http://yann.lecun.com/exdb/mnist/_ , 1998.
  * Li et al. (2018) Ya Li, Mingming Gong, Xinmei Tian, Tongliang Liu, and Dacheng Tao.  Domain generalization via conditional invariant representations.  In _Thirty-Second AAAI Conference on Artificial Intelligence_ , 2018\.
  * Li et al. (2019) Yitong Li, Michael Murias, Samantha Major, Geraldine Dawson, and David Carlson.  On target shift in adversarial domain adaptation.  In _The 22nd International Conference on Artificial Intelligence and Statistics_ , pages 616–625. PMLR, 2019.
  * Lipton et al. (2018) Zachary Lipton, Yu-Xiang Wang, and Alexander Smola.  Detecting and correcting for label shift with black box predictors.  In _International conference on machine learning_ , pages 3122–3130. PMLR, 2018.
  * Magliacane et al. (2018) Sara Magliacane, Thijs van Ommen, Tom Claassen, Stephan Bongers, Philip Versteeg, and Joris M Mooij.  Domain adaptation by using causal inference to predict invariant conditional distributions.  In _Proceedings of the 32nd International Conference on Neural Information Processing Systems_ , pages 10869–10879, 2018.
  * Mansour et al. (2009) Yishay Mansour, Mehryar Mohri, and Afshin Rostamizadeh.  Domain adaptation: Learning bounds and algorithms.  In _22nd Conference on Learning Theory, COLT_ , 2009.
  * McLachlan and Krishnan (2007) Geoffrey J McLachlan and Thriyambakam Krishnan.  _The EM algorithm and extensions_ , volume 382.  John Wiley & Sons, 2007.
  * Meinshausen (2018) Nicolai Meinshausen.  Causality from a distributional robustness point of view.  In _2018 IEEE Data Science Workshop (DSW)_ , pages 6–10. IEEE, 2018\.
  * Muandet et al. (2013) Krikamol Muandet, David Balduzzi, and Bernhard Schölkopf.  Domain generalization via invariant feature representation.  In _International Conference on Machine Learning_ , pages 10–18, 2013\.
  * Neyman (1923) Jerzy Neyman.  Sur les applications de la théorie des probabilités aux experiences agricoles: Essai des principes.  _Roczniki Nauk Rolniczych_ , 10:1–51, 1923.
  * Ni et al. (2019) Jianmo Ni, Jiacheng Li, and Julian McAuley.  Justifying recommendations using distantly-labeled reviews and fine-grained aspects.  In _Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP)_ , pages 188–197, 2019.
  * Nigam et al. (2006) Kamal Nigam, Andrew McCallum, and Tom Mitchell.  Semi-supervised text classification using EM.  _Semi-Supervised Learning_ , pages 33–56, 2006.
  * Pan and Yang (2009) Sinno Jialin Pan and Qiang Yang.  A survey on transfer learning.  _IEEE Transactions on Knowledge and Data Engineering_ , 22(10):1345–1359, 2009.
  * Pan et al. (2010) Sinno Jialin Pan, Ivor W Tsang, James T Kwok, and Qiang Yang.  Domain adaptation via transfer component analysis.  _IEEE Transactions on Neural Networks_ , 22(2):199–210, 2010.
  * Paszke et al. (2019) Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, et al.  Pytorch: An imperative style, high-performance deep learning library.  In _Advances in Neural Information Processing Systems_ , pages 8026–8037, 2019.
  * Pearl (2000) Judea Pearl.  _Causality: models, reasoning and inference_ , volume 29.  Springer, 2000.
  * Pearl and Bareinboim (2014) Judea Pearl and Elias Bareinboim.  External validity: From do-calculus to transportability across populations.  _Statistical Science_ , pages 579–595, 2014.
  * Peng et al. (2019) Xingchao Peng, Qinxun Bai, Xide Xia, Zijun Huang, Kate Saenko, and Bo Wang.  Moment matching for multi-source domain adaptation.  In _Proceedings of the IEEE International Conference on Computer Vision_ , pages 1406–1415, 2019.
  * Peters et al. (2016) Jonas Peters, Peter Bühlmann, and Nicolai Meinshausen.  Causal inference by using invariant prediction: identification and confidence intervals.  _Journal of the Royal Statistical Society: Series B (Statistical Methodology)_ , 78(5):947–1012, 2016.
  * Quionero-Candela et al. (2009) Joaquin Quionero-Candela, Masashi Sugiyama, Anton Schwaighofer, and Neil D Lawrence.  _Dataset shift in machine learning_.  MIT Press, 2009.
  * Raghunathan et al. (2018) Aditi Raghunathan, Jacob Steinhardt, and Percy S Liang.  Semidefinite relaxations for certifying robustness to adversarial examples.  In _Advances in Neural Information Processing Systems_ , pages 10877–10887, 2018.
  * Ratnaparkhi (1996) Adwait Ratnaparkhi.  A maximum entropy model for part-of-speech tagging.  In _Conference on empirical methods in natural language processing_ , 1996.
  * Redko et al. (2020) Ievgen Redko, Emilie Morvant, Amaury Habrard, Marc Sebban, and Younès Bennani.  A survey on domain adaptation theory.  _arXiv preprint arXiv:2004.11829_ , 2020.
  * Rojas-Carulla et al. (2018) Mateo Rojas-Carulla, Bernhard Schölkopf, Richard Turner, and Jonas Peters.  Invariant models for causal transfer learning.  _Journal of Machine Learning Research_ , 19(1):1309–1342, 2018.
  * Rothenhäusler et al. (2019) Dominik Rothenhäusler, Peter Bühlmann, Nicolai Meinshausen, et al.  Causal dantzig: fast inference in linear structural equation models with hidden variables under additive interventions.  _Annals of Statistics_ , 47(3):1688–1722, 2019\.
  * Rothenhäusler et al. (2021) Dominik Rothenhäusler, Nicolai Meinshausen, Peter Bühlmann, and Jonas Peters.  Anchor regression: Heterogeneous data meet causality.  _Journal of the Royal Statistical Society: Series B (Statistical Methodology)_ , 83(2):215–246, 2021.
  * Rubin (1974) Donald B Rubin.  Estimating causal effects of treatments in randomized and nonrandomized studies.  _Journal of Educational Psychology_ , 66(5):688, 1974.
  * Russakovsky et al. (2015) Olga Russakovsky, Jia Deng, Hao Su, Jonathan Krause, Sanjeev Satheesh, Sean Ma, Zhiheng Huang, Andrej Karpathy, Aditya Khosla, Michael Bernstein, et al.  Imagenet large scale visual recognition challenge.  _International Journal of Computer Vision_ , 115(3):211–252, 2015.
  * Schölkopf et al. (2012) Bernhard Schölkopf, Dominik Janzing, Jonas Peters, Eleni Sgouritsa, Kun Zhang, and Joris Mooij.  On causal and anticausal learning.  In _Proceedings of the 29th International Coference on Machine Learning_ , pages 459–466, 2012.
  * Sinha et al. (2018) Aman Sinha, Hongseok Namkoong, and John Duchi.  Certifying some distributional robustness with principled adversarial training.  In _International Conference on Learning Representations_ , 2018.
  * Storkey (2009) Amos Storkey.  When training and test sets are different: characterizing learning transfer.  _Dataset shift in machine learning_ , pages 3–28, 2009.
  * Sugiyama and Kawanabe (2012) Masashi Sugiyama and Motoaki Kawanabe.  _Machine learning in non-stationary environments: Introduction to covariate shift adaptation_.  MIT press, 2012.
  * Tachet des Combes et al. (2020) Remi Tachet des Combes, Han Zhao, Yu-Xiang Wang, and Geoffrey J Gordon.  Domain adaptation with conditional distribution matching and generalized label shift.  _Advances in Neural Information Processing Systems_ , 33, 2020.
  * Wainwright (2019) Martin J Wainwright.  _High-dimensional statistics: A non-asymptotic viewpoint_ , volume 48.  Cambridge University Press, 2019.
  * Wang and Deng (2018) Mei Wang and Weihong Deng.  Deep visual domain adaptation: A survey.  _Neurocomputing_ , 312:135–153, 2018.
  * Wiles et al. (2021) Olivia Wiles, Sven Gowal, Florian Stimberg, Sylvestre Alvise-Rebuffi, Ira Ktena, and Taylan Cemgil.  A fine-grained analysis on distribution shift.  _arXiv preprint arXiv:2110.11328_ , 2021.
  * Wilson and Cook (2020) Garrett Wilson and Diane J Cook.  A survey of unsupervised deep domain adaptation.  _ACM Transactions on Intelligent Systems and Technology (TIST)_ , 11(5):1–46, 2020.
  * Xie et al. (2020) Qizhe Xie, Minh-Thang Luong, Eduard Hovy, and Quoc V Le.  Self-training with noisy student improves imagenet classification.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pages 10687–10698, 2020.
  * Yuan et al. (2019) Zikang Yuan, Dongfu Zhu, Cheng Chi, Jinhui Tang, Chunyuan Liao, and Xin Yang.  Visual-inertial state estimation with pre-integration correction for robust mobile augmented reality.  In _Proceedings of the 27th ACM International Conference on Multimedia_ , pages 1410–1418, 2019.
  * Zhao et al. (2019) Han Zhao, Remi Tachet Des Combes, Kun Zhang, and Geoffrey Gordon.  On learning invariant representations for domain adaptation.  In _International Conference on Machine Learning_ , pages 7523–7532. PMLR, 2019.
  * Zhu (2005) Xiaojin Jerry Zhu.  Semi-supervised learning literature survey.  Technical report, University of Wisconsin-Madison Department of Computer Sciences, 2005.


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

Olivier Hudry
Institut polytechnique de Paris, Télécom Paris, 91123 Palaiseau
& Antoine Lobstein
Laboratoire Interdisciplinaire des Sciences du Numérique
(UMR 9015), CNRS, Université Paris-Saclay, 91400 Orsay
<EMAIL_ADDRESS><EMAIL_ADDRESS>

###### 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 ${\cal 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 ${\cal C}$. As a consequence, these Hamiltonian
problems are NP-hard and belong to the class DP, like U-SAT.

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

##  1 Introduction

###  1.1 The Hamiltonian Cycle and Path Problems

We shall denote by $G=(V,E)$ a finite, simple, undirected graph with vertex
set $V$ and edge set $E$, where an edge between $x\in V$ and $y\in V$ is
indifferently denoted by $xy$ or $yx$. The order of the graph is its number of
vertices, $|V|$.

If $V=\\{v_{1},v_{2},\ldots,v_{n}\\}$, a Hamiltonian path ${\cal
HP}=<v_{i_{1}}v_{i_{2}}\ldots v_{i_{n}}>$ is an ordering of all the vertices
in $V$, such that $v_{i_{j}}v_{i_{j+1}}\in E$ for all $j$, $1\leq j\leq n-1$.
The vertices $v_{i_{1}}$ and $v_{i_{n}}$ are called the ends of ${\cal HP}$. A
Hamiltonian cycle is an ordering ${\cal HC}=<v_{i_{1}}v_{i_{2}}\ldots
v_{i_{n}}(v_{i_{1}})>$ of all the vertices in $V$, such that
$v_{i_{n}}v_{i_{1}}\in E$ and $v_{i_{j}}v_{i_{j+1}}\in E$ for all $j$, $1\leq
j\leq n-1$. Note that the same Hamiltonian cycle admits $2n$ representations,
e.g., $<v_{i_{2}}v_{i_{3}}\ldots v_{i_{n}}v_{i_{1}}(v_{i_{2}})>$ or
$<v_{i_{n}}v_{i_{n-1}}\ldots v_{i_{2}}v_{i_{1}}(v_{i_{n}})>$.

A directed graph $H=(X,A)$ is defined by its set $X$ of vertices and its set
$A$ of directed edges, also called arcs, an arc being an ordered pair $(x,y)$
of vertices; with this respect, $(x,y)$ and $(y,x)$ are two different arcs and
may coexist. A directed graph is said to be oriented if it is antisymmetric,
i.e., if we have, for any pair $\\{x,y\\}$ of vertices, at most one of the two
arcs $(x,y)$ or $(y,x)$; if $(x,y)\in A$, we say that $y$ is the out-neighbour
of $x$, and $x$ is the in-neighbour of $y$, and we define the in-degree and
out-degree of a vertex accordingly. The notions of directed Hamiltonian cycle
and of directed Hamiltonian path are extended to a directed graph by
considering the arcs $(v_{i_{n}},v_{i_{1}})\in A$ and
$(v_{i_{j}},v_{i_{j+1}})\in A$ in the above definitions. When there is no
ambiguity, we shall often drop the words “directed” and “Hamiltonian”.

The following six problems (stated as one) are well known, in graph theory as
well as in complexity theory:

Problem HAMC / HAMP (Hamiltonian Cycle / Hamiltonian Path):
Instance: An undirected, directed or oriented graph.
Question: Does the graph admit a Hamiltonian cycle / Hamiltonian path?

As we shall see (Proposition 2), they have been known to be NP-complete for a
long time. In this paper, we shall be interested in the following problems,
and shall locate them in the complexity classes:

Problem U-HAMC[U] (Unique Hamiltonian Cycle in an Undirected graph):
Instance: An undirected graph $G=(V,E)$.
Question: Does $G$ admit a unique Hamiltonian cycle?

Problem U-HAMP[U] (Unique Hamiltonian Path in an Undirected graph):
Instance: An undirected graph $G=(V,E)$.
Question: Does $G$ admit a unique Hamiltonian path?

Problem U-HAMC[D] (Unique directed Hamiltonian Cycle in a Directed graph):
Instance: A directed graph $H=(X,A)$.
Question: Does $H$ admit a unique directed Hamiltonian cycle?

Problem U-HAMP[D] (Unique directed Hamiltonian Path in a Directed graph):
Instance: A directed graph $H=(X,A)$.
Question: Does $H$ admit a unique directed Hamiltonian path?

Problem U-HAMC[O] (Unique directed Hamiltonian Cycle in an Oriented graph):
Instance: An oriented graph $H=(X,A)$.
Question: Does $H$ admit a unique directed Hamiltonian cycle?

Problem U-HAMP[O] (Unique directed Hamiltonian Path in an Oriented graph):
Instance: An oriented graph $H=(X,A)$.
Question: Does $H$ admit a unique directed Hamiltonian path?

We shall prove in Section 2 that these problems have the same complexity, up
to polynomials, as the problem of the uniqueness of a truth assignment
satisfying a Boolean formula (U-SAT). As a consequence, all are NP-hard and
belong to the class DP. The closely related problem Unique Optimal Travelling
Salesman has been investigated in [13], see Remark 8.

In similar works, we reexamine some famous problems, from the viewpoint of
uniqueness of solution: Vertex Cover and Dominating Set (as well as its
generalization to domination within distance $r$) [8], $r$-Identifying Code
together with $r$-Locating-Dominating Code [9], and Graph Colouring and
Boolean Satisfiability [10]. We shall re-use here results from [10], and
modify a construction from [8].

In the sequel, we shall need the following tools, which constitute classical
definitions related to graph theory or to Boolean satisfiability. A vertex
cover in an undirected graph $G$ is a subset of vertices $V^{*}\subseteq V$
such that for every edge $e=uv\in E$, $V^{*}\cap\\{u,v\\}\neq\emptyset$. We
denote by $\phi(G)$ the smallest cardinality of a vertex cover of $G$; any
vertex cover $V^{*}$ with $|V^{*}|=\phi(G)$ is said to be optimal.

Next we consider a set ${\cal X}$ of $n$ Boolean variables $x_{i}$ and a set
${\cal C}$ of $m$ clauses (${\cal C}$ is also called a Boolean formula); each
clause $c_{j}$ contains $\kappa_{j}$ literals, a literal being a variable
$x_{i}$ or its complement $\overline{x}_{i}$. A truth assignment for ${\cal
X}$ sets the variable $x_{i}$ to TRUE, also denoted by T, and its complement
to FALSE (or F), or vice-versa. A truth assignment is said to satisfy the
clause $c_{j}$ if $c_{j}$ contains at least one true literal, and to satisfy
the set of clauses ${\cal C}$ if every clause contains at least one true
literal. The following decision problems are classical problems in complexity.

Problem VC (Vertex Cover with bounded size):
Instance: An undirected graph $G$ and an integer $k$.
Question: Does $G$ admit a vertex cover of size at most $k$?

Problem SAT (Satisfiability):
Instance: A set ${\cal X}$ of variables, a collection ${\cal C}$ of clauses
over ${\cal X}$, each clause containing at least two different literals.
Question: Is there a truth assignment for ${\cal X}$ that satisfies ${\cal
C}$?

The following problem is stated for any fixed integer $k\geq 2$.

Problem $k$-SAT ($k$-Satisfiability):
Instance: A set ${\cal X}$ of variables, a collection ${\cal C}$ of clauses
over ${\cal X}$, each clause containing exactly $k$ different literals.
Question: Is there a truth assignment for ${\cal X}$ that satisfies ${\cal
C}$?

Problem 1-3-SAT (One-in-Three Satisfiability):
Instance: A set ${\cal X}$ of variables, a collection ${\cal C}$ of clauses
over ${\cal X}$, each clause containing exactly three different literals.
Question: Is there a truth assignment for ${\cal X}$ such that each clause of
${\cal C}$ contains exactly one true literal?

We shall say that a clause (respectively, a set of clauses) is 1-3-satisfied
by an assignment if this clause (respectively, every clause in the set)
contains exactly one true literal. We shall also consider the following
variants of the above problems:

U-VC (Unique Vertex Cover with bounded size),

U-SAT (Unique Satisfiability),

U-$k$-SAT (Unique $k$-Satisfiability),

U-1-3-SAT (Unique One-in-Three Satisfiability).

They have the same instances as VC, SAT, $k$-SAT and 1-3-SAT respectively, but
now the question is “Is there a unique vertex cover / truth
assignment$\ldots$?”.

We shall give in Propositions 3–7 what we need to know about the complexities
of these problems.

###  1.2 Some Classes of Complexity

We refer the reader to, e.g., [1], [6], [11] or [14] for more on this topic. A
decision problem is of the type “Given an instance $I$ and a property ${\cal
PR}$ on $I$, is ${\cal PR}$ true for $I$?”, and has only two solutions, “yes”
or “no”. The class P will denote the set of problems which can be solved by a
polynomial (time) algorithm, and the class NP the set of problems which can be
solved by a nondeterministic polynomial algorithm. A polynomial reduction from
a decision problem $\pi_{1}$ to a decision problem $\pi_{2}$ is a polynomial
transformation that maps any instance of $\pi_{1}$ into an equivalent instance
of $\pi_{2}$, that is, an instance of $\pi_{2}$ admitting the same answer as
the instance of $\pi_{1}$; in this case, we shall write
$\pi_{1}\leqslant_{p}\pi_{2}$. Cook [4] proved that there is one problem in
NP, namely SAT, to which every other problem in NP can be polynomially
reduced. Thus, in a sense, SAT is the “hardest” problem inside NP. Other
problems share this property in NP and are called NP-complete problems; their
class is denoted by NP-C. The way to show that a decision problem $\pi$ is NP-
complete is, once it is proved to be in NP, to choose some NP-complete problem
$\pi_{1}$ and to polynomially reduce it to $\pi$. From a practical viewpoint,
the NP-completeness of a problem $\pi$ implies that we do not know any
polynomial algorithm solving $\pi$, and that, under the assumption
P$\,\neq\,$NP, which is widely believed to be true, no such algorithm exists:
the time required can grow exponentially with the size of the instance (when
the instance is a graph, its size is polynomially linked to its order; for a
Boolean formula, the size is polynomially linked to, e.g., the number of
variables plus the number of clauses).

The complement of a decision problem, “Given $I$ and ${\cal PR}$, is ${\cal
PR}$ true for $I$?”, is “Given $I$ and ${\cal PR}$, is ${\cal PR}$ false for
$I$?”. The class co-NP (respectively, co-NP-C) is the class of the problems
which are the complement of a problem in NP (respectively, NP-C).

For problems which are not necessarily decision problems, a Turing reduction
from a problem $\pi_{1}$ to a problem $\pi_{2}$ is an algorithm ${\cal A}$
that solves $\pi_{1}$ using a (hypothetical) subprogram ${\cal S}$ solving
$\pi_{2}$ such that, if ${\cal S}$ were a polynomial algorithm for $\pi_{2}$,
then ${\cal A}$ would be a polynomial algorithm for $\pi_{1}$. Thus, in this
sense, $\pi_{2}$ is “at least as hard” as $\pi_{1}$. A problem $\pi$ is NP-
hard (respectively, co-NP-hard) if there is a Turing reduction from some NP-
complete (respectively, co-NP-complete) problem to $\pi$ [6, p. 113].

###### Remark 1

Note that with these definitions, NP-hard and co-NP-hard coincide [6, p. 114].

The notion of completeness can of course be extended to classes other than NP
or co-NP. Observe that NP-hardness is defined differently in [5] and [7]:
there, a problem $\pi$ is NP-hard if there is a polynomial reduction from some
NP-complete problem to $\pi$; this may lead to confusion (see Section 3).

We also introduce the classes PNP (also known as $\Delta_{2}$ in the hierarchy
of classes) and LNP (also denoted by PNP[O(logn)] or $\Theta_{2}$), which
contain the decision problems which can be solved by applying, with a number
of calls which is polynomial (respectively, logarithmic) with respect to the
size of the instance, a subprogram able to solve an appropriate problem in NP
(usually, an NP-complete problem); and the class DP [15] (or DIFP [2] or BH2
[11], [17]$,~{}\ldots$) as the class of languages (or problems) $L$ such that
there are two languages $L_{1}\in\,$NP and $L_{2}\in\,$co-NP satisfying
$L=L_{1}\cap L_{2}$ (in Figure 1, DP-C and $P^{NP}$-C denote respectively the
class of the DP-complete problems and the class of the $P^{NP}$-complete
problems). This class is not to be confused with NP$\,\cap\,$co-NP (see the
warning in, e.g., [14, p. 412]); actually, DP contains NP$\,\cup\,$co-NP and
is contained in LNP. See Figure 1.

Figure 1: Some classes of complexity.

Membership to P, NP, co-NP, DP, LNP or PNP gives an upper bound on the
complexity of a problem (this problem is not more difficult than $\ldots$),
whereas a NP-hardness result gives a lower bound (this problem is at least as
difficult as any problem belonging to NP or to co-NP). Still, such results are
conditional in the sense that we do not know whether or where the classes of
complexity collapse.

We now consider some of the problems from Section 1.1.

###### Proposition 2

[12], [6, pp. 56–60 and pp. 199-200] The decision problems HAMC and HAMP, in
an undirected, directed or oriented graph, are NP-complete. $\Diamond$

The problems VC, SAT and 3-SAT are also three of the basic and most well-known
NP-complete problems [4], [6, p. 39, p. 46, p. 190 and p. 259]. More
generally, $k$-SAT is NP-complete for $k\geq 3$ and polynomial for $k=2$. The
problem 1-3-SAT, which is obvioulsy in NP, is also NP-complete [16, Lemma
3.5], [6, p. 259], [10, Rem. 3].

The following results will be used in the sequel.

###### Proposition 3

[10] For every integer $k\geq 3$, the decision problems U-SAT, U-$k$-SAT and
U-$1$-$3$-SAT have equivalent complexity, up to polynomials. $\Diamond$

Using the previous proposition and results from [2] and [14, p. 415], it is
rather simple to obtain the following two results.

###### Proposition 4

For every integer $k\geq 3$, the decision problems U-SAT, U-$k$-SAT and
U-$1$-$3$-SAT are co-NP-hard and thus NP-hard by Remark 1. $\Diamond$

###### Proposition 5

For every integer $k\geq 3$, the decision problems U-SAT, U-$k$-SAT and
U-$1$-$3$-SAT belong to the class DP. $\Diamond$

###### Remark 6

It is not known whether these problems are DP-complete. In [14, p. 415], it is
said that “U-SAT is not believed to be DP-complete”.

###### Proposition 7

[8] The decision problems U-SAT and U-VC have equivalent complexity, up to
polynomials. In particular, there exists a polynomial reduction from
U-$1$-$3$-SAT to U-VC: U-$1$-$3$-SAT $\leqslant_{p}$ U-VC. $\Diamond$

After the following remark is made, we shall be ready to investigate the
problems of uniqueness of Hamiltonian cycle or path.

###### Remark 8

In [13], it is shown that the following problem is PNP-complete (or
$\Delta_{2}$-complete).

Problem U-OTS (Unique Optimal Travelling Salesman):
Instance: A set of $n$ vertices, a $n\times n$ symmetric matrix $[c_{ij}]$ of
(nonnegative) integers giving the distance between any two vertices $i$ and
$j$.
Question: Is there a unique optimal tour, that is, a unique way of visiting
every vertex exactly once and coming back, with the smallest distance sum?

At best, a polynomial reduction from any instance $G=(V,E)$ of U-HAMC[U] to
U-OTS would show that U-HAMC[U] belongs to PNP, but we have a better result in
Theorem 15(b), with U-HAMC[U] belonging to DP; no useful information for our
Hamiltonian problems can be induced from this result on U-OTS.

##  2 Locating the Problems of Uniqueness

We prove that our six Hamiltonian problems have the same complexity as any of
the three problems U-SAT, U-$k$-SAT ($k\geq 3$) and U-1-3-SAT by proving the
chain of polynomial reductions given by Figure 2.

Figure 2: The chain of polynomial reductions, where an arrow from $\pi_{1}$ to
$\pi_{2}$ stands for the relation $\pi_{1}\leqslant_{p}\pi_{2}$.

###### Theorem 9

There exists a polynomial reduction from U-$1$-$3$-SAT to U-HAMP[O]:
U-$1$-$3$-SAT $\leqslant_{p}$ U-HAMP[O].

Proof. A polynomial reduction from the problem U-1-3-SAT to U-HAMP[O], via
U-VC, can be found in the Appendix; it is an elaborate variation on the
polynomial reduction from 3-SAT to VC in [12], [6, pp. 54–56] and the
polynomial reduction from VC to HAMC[U] (see [6, pp. 56–60]). $\Diamond$

###### Proposition 10

There exists a polynomial reduction from U-HAMP[O] to U-HAMC[O]: U-HAMP[O]
$\leqslant_{p}$ U-HAMC[O].

Proof. We start from an oriented graph $H=(X,A)$ which is an instance of
U-HAMP[O] and build a graph which is an instance of U-HAMC[O] by adding two
extra vertices $y,\,z$, together with the arc $(y,z)$ and all the arcs $(x,y)$
and $(z,x)$, $x\in X$. This transformation is polynomial and clearly preserves
the number of solutions, in particular the uniqueness. $\Diamond$

###### Proposition 11

There is a polynomial reduction from U-HAMP[O] to U-HAMP[D] and from U-HAMC[O]
to U-HAMC[D]:

U-HAMP[O] $\leqslant_{p}$ U-HAMP[D] and U-HAMC[O] $\leqslant_{p}$ U-HAMC[D].

Proof. It suffices to consider the identity as the polynomial reduction.
$\Diamond$

###### Theorem 12

There is a polynomial reduction from U-HAMP[D] to U-HAMP[U] and from U-HAMC[D]
to U-HAMC[U]:

U-HAMP[D] $\leqslant_{p}$ U-HAMP[U] and U-HAMC[D] $\leqslant_{p}$ U-HAMC[U].

Proof. The method is borrowed from [12].

Consider any instance of U-HAMP[D] or U-HAMC[D], i.e., a directed graph
$H=(X,A)$ on $n$ vertices. We build the undirected graph $G=(V,E)$, the
instance of U-HAMP[U] or U-HAMC[U], as follows: every vertex $x\in X$ is
triplicated into three vertices $x^{-}\in V$ (a minus-type vertex), $x^{*}\in
V$ (a star-type vertex) and $x^{+}\in V$, linked by the edges $x^{-}x^{*}\in
E$ and $x^{*}x^{+}\in E$; for every arc $(x,y)\in A$, we create the edge
$x^{+}y^{-}$ in $E$. The graph $G$ thus constructed has order $3n$.

We claim that there is a unique Hamiltonian cycle (respectively, path) in $G$
if and only if there is a unique directed Hamiltonian cycle (respectively,
path) in $H$.

(1) Assume first that $H$ admits a directed Hamiltonian cycle
$<x_{1}x_{2}\ldots$ $x_{n}(x_{1})>$. Then

$<x_{1}^{-}x^{*}_{1}x_{1}^{+}x_{2}^{-}x^{*}_{2}x_{2}^{+}\ldots
x_{n-1}^{+}x_{n}^{-}x^{*}_{n}x_{n}^{+}(x_{1}^{-})>$

is a Hamiltonian cycle in $G$. Moreover, two different directed Hamiltonian
cycles in $H$ provide two different Hamiltonian cycles in $G$.

Conversely, assume that $G$ admits a Hamiltonian cycle ${\cal HC}$. This cycle
must go through all the star-type vertices $x^{*}$, so it necessarily goes
through all the edges $x^{-}x^{*}$ and $x^{*}x^{+}$. Without loss of
generality, ${\cal HC}$ reads:

${\cal HC}=<x_{1}^{-}x^{*}_{1}x_{1}^{+}x_{2}^{-}x^{*}_{2}x_{2}^{+}\ldots
x_{n-1}^{+}x_{n}^{-}x^{*}_{n}x_{n}^{+}(x_{1}^{-})>\,;$ (1)

indeed, we may assume that we “start” with the edge $x_{1}^{-}x_{1}^{*}$, then
$x_{1}^{*}x_{1}^{+}$; now, because the edges which have no star-type vertex as
one of their extremities are necessarily of the type $x^{+}y^{-}$, the other
neighbour of $x_{1}^{+}$ is a minus-type vertex, say $x_{2}^{-}$; step by
step, we see that ${\cal HC}$ has necessarily the previous form (1). Now we
claim that $<x_{1}x_{2}\ldots x_{n-1}x_{n}(x_{1})>$ is a directed Hamiltonian
cycle in $H$.

Indeed, for every $i\in\\{1,\ldots,n-1\\}$, the edge $x_{i}^{+}x_{i+1}^{-}$ in
$G$ implies the existence of the arc $(x_{i},x_{i+1})$ in $H$; the same is
true for the arc $(x_{n},x_{1})$ in $H$, thanks to the edge
$x_{n}^{+}x_{1}^{-}$ in $G$. Furthermore, observe that two different
Hamiltonian cycles in $G$ provide two different directed Hamiltonian cycles in
$H$.

So, $G$ admits a unique Hamiltonian cycle if and only if $H$ admits a unique
directed Hamiltonian cycle.

(2) Exactly the same argument works with paths, apart from the fact that we
need not consider the arc $(x_{n},x_{1})$ in $H$, nor the edge
$x_{n}^{+}x_{1}^{-}$ in $G$. $\Diamond$

###### Proposition 13

There exists a polynomial reduction from U-HAMP[U] to U-HAMC[U]: U-HAMP[U]
$\leqslant_{p}$ U-HAMC[U].

Proof. We start from an undirected graph $G=(V,E)$ which is an instance of
U-HAMP[U] and build a graph which is an instance of U-HAMC[U] by adding the
extra vertex $y$, together with all the edges $xy$, $x\in V$. This
transformation is polynomial and clearly preserves the number of solutions, in
particular the uniqueness. $\Diamond$

###### Theorem 14

There exists a polynomial reduction from U-HAMC[U] to U-SAT: U-HAMC[U]
$\leqslant_{p}$ U-SAT.

Proof. We start from an instance of U-HAMC[U], an undirected graph $G=(V,E)$
with $V=\\{x^{1},\ldots,x^{|V|}\\}$; we assume that $|V|\geq 3$. We create the
set of variables ${\cal X}=\\{x^{i}_{j}:1\leq j\leq|V|,1\leq i\leq|V|\\}$ and
the following clauses:

(a1) for $1\leq i\leq|V|$, clauses of size $|V|$:
$\\{x^{i}_{1},x^{i}_{2},\ldots,x^{i}_{|V|}\\}$;

(a2) for $1\leq i\leq|V|$, $1\leq j<j^{\prime}\leq|V|$, clauses of size two:
$\\{{\overline{x}}^{i}_{j},{\overline{x}}^{i}_{j^{\prime}}\\}$;

(b1) for $1\leq j\leq|V|$, clauses of size $|V|$:
$\\{x_{j}^{1},x_{j}^{2},\ldots,x_{j}^{|V|}\\}$;

(b2) for $1\leq i<i^{\prime}\leq|V|$, $1\leq j\leq|V|$, clauses of size two:
$\\{{\overline{x}}^{i}_{j},{\overline{x}}^{i^{\prime}}_{j}\\}$;

(c) for $1\leq i<i^{\prime}\leq|V|$ such that $x^{i}x^{i^{\prime}}\notin E$,
for $1\leq j\leq|V|$, clauses of size two:
$\\{{\overline{x}}^{i}_{j},{\overline{x}}^{i^{\prime}}_{j+1}\\}$ and
$\\{{\overline{x}}^{i}_{j},{\overline{x}}^{i^{\prime}}_{j-1}\\}$, with
computations performed modulo $|V|$;

(d1) $\\{x^{1}_{1}\\}$;

(d2) for $2\leq j<j^{\prime}\leq|V|$, clauses of size two:
$\\{{\overline{x}}^{2}_{j^{\prime}},{\overline{x}}^{3}_{j}\\}$.

Assume that we have a unique Hamiltonian cycle in $G$, ${\cal
HC}_{1}=<x^{p_{1}}x^{p_{2}}x^{p_{3}}$ $\ldots
x^{p_{|V|-1}}x^{p_{|V|}}(x^{p_{1}})>$. Note that for the time being, we could
also write ${\cal HC}_{1}=<x^{p_{1}}x^{p_{|V|}}x^{p_{|V|-1}}\ldots
x^{p_{3}}x^{p_{2}}(x^{p_{1}})>$, or “start” on a vertex other than
$x^{p_{1}}$, cf. Introduction. This is why, without loss of generality, we set
$p_{1}=1$, i.e., we “fix” the first vertex, and we also choose the “direction”
of the cycle, by deciding, e.g., that $x^{2}$ appears “before” $x^{3}$ in the
cycle —cf. (d1)-(d2). Define the assignment ${\cal A}_{1}$ by ${\cal
A}_{1}(x^{p_{q}}_{q})=\,$T for $1\leq q\leq|V|$, and all the other variables
are set FALSE by ${\cal A}_{1}$. We claim that ${\cal A}_{1}$ satisfies all
the clauses.

(a1) for $1\leq i\leq|V|$, if the vertex $x^{i}$ has position $j$ in the
cycle, then the variable $x^{i}_{j}$ satisfies the clause; (a2) if
$\\{{\overline{x}}^{i}_{j},{\overline{x}}^{i}_{j^{\prime}}\\}$ is not
satisfied by ${\cal A}_{1}$ for some $i,j,j^{\prime}$, then ${\cal
A}_{1}(x^{i}_{j})={\cal A}_{1}(x^{i}_{j^{\prime}})=\,$T, which means that the
vertex $x^{i}$ appears at least twice in the cycle;

(b1) for $1\leq j\leq|V|$, if the position $j$ is occupied by the vertex
$x^{i}$, then the variable $x^{i}_{j}$ satisfies the clause; (b2) if
$\\{{\overline{x}}^{i}_{j},{\overline{x}}^{i^{\prime}}_{j}\\}$ is not
satisfied by ${\cal A}_{1}$ for some $i,i^{\prime},j$, then two different
vertices are the $j$-th vertex in the cycle.

(c) If one of the two clauses is not satisfied, say the first one, then the
positions $j$ and $j+1$ in the cycle are occupied by two vertices not linked
by any edge in $G$.

(d1) $\\{x^{1}_{1}\\}$ is satisfied by ${\cal A}_{1}$ thanks to the assumption
on the first vertex of the cycle; (d2) if for some $j<j^{\prime}$, the clause
$\\{{\overline{x}}^{2}_{j^{\prime}},{\overline{x}}^{3}_{j}\\}$ is not
satisfied, then the vertex $x^{3}$ occupies a position $j$ smaller than the
position $j^{\prime}$ of $x^{2}$, which contradicts our assumption on $x^{2}$
and $x^{3}$.

Is ${\cal A}_{1}$ unique? Assume on the contrary that another assignment,
${\cal A}_{2}$, also satisfies the constructed instance of U-SAT. Then by (a1)
and (a2), for every $i\in\\{1,\ldots,|V|\\}$, there is at least, then at most,
one $j=j(i)$ such that ${\cal A}_{2}(x^{i}_{j})=\,$T; by (b1) and (b2), for
every $j\in\\{1,\ldots,|V|\\}$, there is at least, then at most, one $i=i(j)$
such that ${\cal A}_{2}(x^{i}_{j})=\,$T; so we have “a place for everything
and everything in its place”, with exactly $|V|$ variables which are TRUE by
${\cal A}_{2}$ and an ordering of the vertices according to the one-to-one
correspondence given by ${\cal A}_{2}$: the vertex $x^{i}$ is in position $j$
if and only if ${\cal A}_{2}(x^{i}_{j})=\,$T. Next, thanks to the clauses (c),
two vertices following each other in this ordering, including the last and
first ones, are necessarily neighbours, so that this ordering is a Hamiltonian
cycle, ${\cal HC}_{2}$. Since we have assumed the uniqueness of the
Hamiltonain cycle ${\cal HC}_{1}$ in $G$, the two cycles can differ only by
their starting points or their “directions”. However these differences are
ruled out by the clauses (d1) and (d2), so that the two cycles coincide vertex
to vertex, and ${\cal A}_{1}={\cal A}_{2}$. So a YES answer for U-HAMC[U]
leads to a YES answer for U-SAT.

Assume now that the answer to U-HAMC[U] is negative. If it is negative because
there are at least two Hamiltonian cycles, then we have at least two
assignments satisfying the instance of U-SAT: we have seen above how to
construct a suitable assignment from a cycle, and different cycles obviously
lead to different assignments. If there is no Hamiltonian cycle, then there is
no assignment satisfying U-SAT, because such an assignment would give a cycle,
as we have seen above with ${\cal A}_{2}$. So in both cases, a NO answer to
U-HAMC[U] implies a NO answer to U-SAT. $\Diamond$

Gathering all our previous results, we obtain the following theorem.

###### Theorem 15

For every integer $k\geq 3$, the decision problems U-SAT, U-$k$-SAT and
U-$1$-$3$-SAT have the same complexity as U-HAMP[U], U-HAMC[U], U-HAMP[O],
U-HAMC[O], U-HAMP[D], and U-HAMC[D], up to polynomials. Therefore,

(a) the decision problems U-HAMP[U], U-HAMC[U], U-HAMP[O], U-HAMC[O],
U-HAMP[D], and U-HAMC[D] are co-NP-hard and thus NP-hard by Remark 1;

(b) the decision problems U-HAMP[U], U-HAMC[U], U-HAMP[O], U-HAMC[O],
U-HAMP[D], and U-HAMC[D] belong to the class DP. $\Diamond$

Note that the membership to DP could have been proved directly.

##  3 Conclusion

By Theorem 15, for every integer $k\geq 3$, the three decision problems U-SAT,
U-$k$-SAT, U-$1$-$3$-SAT have the same complexity, up to polynomials, as the
problem of the uniqueness of a path or of a cycle in a graph, undirected,
directed, or oriented; all are co-NP-hard (and NP-hard by Remark 1) and belong
to the class DP, and it is thought that they are not DP-complete. Anyway, they
can be found somewhere in the shaded area of Figure 3.

Open problem. Find a better location for any of these problems inside the
hierarchy of complexity classes.

Figure 3: Some classes of complexity: Figure 1 re-visited.

In [2], the authors wonder whether

(A) U-SAT is NP-hard, but here we believe that what they mean is: does there
exist a polynomial reduction from an NP-complete problem to U-SAT ? i.e., they
use the second definition of NP-hardness;

finally, they show that (A) is true if and only if

(B) U-SAT is DP-complete.

So, if one is careless and considers that U-SAT is NP-hard without checking
according to which definition, one might easily jump too hastily to the
conclusion that U-SAT is DP-complete, which, to our knowledge, is not known to
be true or not. As for U-3-SAT, we do not know where to locate it more
precisely either; in [3] the problems U-$k$-SAT and more particularly U-3-SAT
are studied, but it appears that they are versions where the given set of
clauses has zero or one solution, which makes quite a difference with our
problem.

Appendix: the Proof of Theorem 9

A) From U-1-3-SAT to U-VC
From an arbitrary instance of U-1-3-SAT with $m$ clauses and $n$ variables, we
mimick the reduction from 3-SAT to VC in [12], [6, pp. 54–56], and we
construct the instance $G_{VC}=(V_{VC},E_{VC})$ of U-VC as follows (see Figure
4 for an example): we construct for each clause $c_{j}$ a triangle
$T_{j}=\\{a_{j},b_{j},d_{j}\\}$, and for each variable $x_{i}$ a component
$G_{i}=(V_{i}=\\{x_{i},\overline{x}_{i}\\},E_{i}=\\{x_{i}\overline{x}_{i}\\})$.
Then we link the components $G_{i}$ on the one hand, and the triangles $T_{j}$
on the other hand, according to which literals appear in which clauses
(“membership edges”). For each clause
$c_{j}=\\{\ell_{1},\ell_{2},\ell_{3}\\}$, we also add the triangular set of
edges
$E^{\prime}_{j}=\\{\overline{\ell}_{1}\overline{\ell}_{2},\overline{\ell}_{1}\overline{\ell}_{3},\overline{\ell}_{2}\overline{\ell}_{3}\\}$.
Finally, we set $k=n+2m$.

Figure 4: Illustration of the undirected graph constructed for the reduction
from U-1-3-SAT to U-VC, with four variables and two clauses,
$c_{1}=\\{x_{1},x_{2},x_{3}\\}$, $c_{2}=\\{\overline{x}_{2},x_{3},x_{4}\\}$.
Here, $k=8$, and the black vertices form the (not unique) vertex cover $V^{*}$
of size eight corresponding to the (not unique) truth assignment $x_{1}=\,$T,
$x_{2}=\,$F, $x_{3}=\,$F, $x_{4}=\,$F 1-3-satisfying the clauses. As soon as
we set $V^{*}\cap(V_{1}\cup V_{2}\cup V_{3}\cup
V_{4})=\\{x_{1},\overline{x}_{2},\overline{x}_{3},\overline{x}_{4}\\}$, the
other vertices in $V^{*}$ are forced.

The order of $G_{VC}$ is $3m+2n$ and its number of edges is at most $n+9m$
(the edge sets $E^{\prime}_{j}$ are not necessarily disjoint).

Note already that if $V^{*}$ is a vertex cover, then each triangle $T_{j}$
contains at least two vertices, each component $G_{i}$ at least one vertex,
and $|V^{*}|\geq 2m+n=k$; if $|V^{*}|=2m+n$, then each triangle contains
exactly two vertices, and each component $G_{i}$ exactly one vertex. We can
also observe that, because of the edge sets $E^{\prime}_{j}$, at least two
vertices among $\overline{\ell}_{1},\overline{\ell}_{2},\overline{\ell}_{3}$
belong to any vertex cover.

(a) Let us first assume that the answer to U-1-3-SAT is YES: there is a unique
truth assignment 1-3-satisfying the clauses of ${\cal C}$. Then, by taking, in
each $G_{i}$, the vertex corresponding to the literal which is TRUE, and in
every triangle $T_{j}$, the two vertices which are linked to the two false
literals of $c_{j}$, we obtain a vertex cover $V^{*}$ whose size is equal to
$k$. Moreover, once we have put the $n$ vertices corresponding to the true
literals in the vertex cover $V^{*}$ in construction, we have no choice for
the completion of $V^{*}$ with $k-n=2m$ vertices: when we take two vertices in
$T_{j}$, we must take the two vertices which cover the membership edges linked
to the two false literals (in the example of Figure 4, the vertices
$b_{1},d_{1}$ and $b_{2},d_{2}$). So, if another vertex cover $V^{+}$ of size
$k$ exists, it must have a different distribution of its vertices over the
components $G_{i}$, still with exactly one vertex in each $G_{i}$; this in
turn defines a valid truth assignment, by setting $x_{i}=\,$T if $x_{i}\in
V^{+}$, $x_{i}=\,$F if $\overline{x}_{i}\in V^{+}$. Now this assignment
1-3-satisfies ${\cal C}$, thanks in particular to our observation on the
covering of the edges in $E^{\prime}_{j}$. So we have two truth assignments
1-3-satisfying ${\cal C}$, contradicting the YES answer to U-1-3-SAT;
therefore, $V^{*}$ is the only vertex cover of size $k$.

(b) Assume next that the answer to U-1-3-SAT is NO: this may be either because
no truth assignment 1-3-satisfies the instance, or because at least two
assignments do; in the latter case, this would lead, using the same argument
as in the previous paragraph, to at least two vertex covers of size $k$, and a
NO answer to U-VC. So we are left with the case when the set of clauses ${\cal
C}$ cannot be 1-3-satisfied. But again, we have already seen that this would
imply that no vertex cover of size (at most) $k$ exists, since such a
hypothetical vertex cover $V^{+}$ would imply the existence of a suitable
assignment.

We are now ready to construct an instance of U-HAMP[O]. In the sequel, we
shall say “path” for “directed Hamiltonian path”.

B) Construction of the Instance of U-HAMP[O]
We look deeper into the proof of the NP-completeness of the problem
Hamiltonian Cycle (see [6, pp. 56–60]), which uses a polynomial reduction from
VC to HAMC[U] that, due to the so-called “selector vertices”, cannot cope with
the problem of uniqueness; step by step, we construct an oriented graph
$H=(X,A)$ for which we will prove that:

(i) if there is a YES answer for the instance of U-1-3-SAT (which implies that
there is a unique vertex cover $V^{*}$ in $G_{VC}$, with cardinality at most
$k$), then there is a unique path in $H$;

(ii) if there are at least two assignments 1-3-satisfying all the clauses
(i.e., there are at least two vertex covers in $G_{VC}$, with cardinality at
most $k$), then there are at least two paths in $H$;

(iii) if there is no assignment 1-3-satisfying the clauses (and no vertex
cover in $G_{VC}$ with cardinality at most $k$), then there is no path in $H$.

Step 1. For each edge $e=uv\in E_{VC}$, we build one component
$H_{e}=(X_{e},A_{e})$ with 12 vertices and 14 arcs:
$X_{e}=\\{(u,e,i),(v,e,i):1\leq i\leq 6\\}$,
$A_{e}=\\{((u,e,i),(u,e,i+1)),((v,e,i),(v,e,i+1)):1\leq i\leq
5\\}\cup\\{((v,e,3),(u,e,1)),$
$((u,e,3),(v,e,1))\\}\cup\\{((v,e,6),(u,e,4)),((u,e,6),(v,e,4))\\}$; see
Figure 5, which is the oriented copy of Figure 3.4 in [6, p. 57].

Figure 5: Two possible representations of the same component $H_{e}$ for the
edge $e=uv\in E_{VC}$ (Step 1).

In the completed construction, the only vertices from this component that will
be involved in any additional arcs are the vertices $(u,e,1)$, $(u,e,6)$,
$(v,e,1)$, and $(v,e,6)$. This, together with the fact that there will be two
particular vertices, $\alpha_{1}$ and $\delta$, which will necessarily be the
ends of any path, will imply that any path in the final graph $H$ will have to
meet the vertices in $X_{e}$ in exactly one of the three configurations shown
in Figure 6, which is the oriented copy of Figure 3.5, in [6, p. 58]. Thus,
when the path meets the component $H_{e}$ at $(u,e,1)$, it will have to leave
at $(u,e,6)$ and go through either (a) all 12 vertices in the component, in
which case we shall say that the component is completely visited from the
$u$-side, or (b) only the 6 vertices $(u,e,i)$, $1\leq i\leq 6$, in which case
we shall say that the component is visited in parallel and needs two visits,
i.e., another section of the path will re-visit the component, meeting the 6
vertices $(v,e,i)$, $1\leq i\leq 6$.

Figure 6: The three ways of going through the component $H_{e}$ (Step 1). The
arrows inside $H_{e}$ are not represented.

Step 2. We create $n$ vertices $\alpha_{i}$, $1\leq i\leq n$, and $2n$ arcs
$(\alpha_{i},(x_{i},x_{i}\overline{x}_{i},1))$,
$(\alpha_{i},(\overline{x}_{i},x_{i}\overline{x}_{i},1))$, that is, we link
$\alpha_{i}$ to the “first” vertices of the component $H_{e}$ whenever
$e=x_{i}\overline{x}_{i}$. The vertices $\alpha_{i}$ can be seen as literal
selectors that will choose between $x_{i}$ and $\overline{x}_{i}.$ The vertex
$\alpha_{1}$ will have no other neighbours; this means in particular that it
will have no in-neighbours, thus it will necessarily be the starting vertex of
any Hamiltonian path, if such a path exists.

We choose an arbitrary order on the $3m$ vertices of the triangles $T_{j}$ in
the graph $G_{VC}$, say ${\cal O}_{T}=<a_{1},b_{1},d_{1},a_{2},\ldots,d_{m}>$
and an arbitrary order on the literals $x_{i},\overline{x}_{i}$, say ${\cal
O}_{\ell}=<x_{1},x_{2},\ldots,x_{n},\overline{x}_{1},\ldots,\overline{x}_{n}>$.
For each literal $\ell_{i}$ equal to $x_{i}$ or $\overline{x}_{i}$, we do the
following (see Figure 7 for an example):

Figure 7: The example of the literals $x_{1}$ and $\overline{x}_{1}$ from
Figure 4 (Step 2); here, Rule (a) applies with $q(x_{1})=1$,
$q(\overline{x}_{1})=0$, Rule (b) with $s(\overline{x}_{1})=2$. The arrows
inside $H_{e}$ are not represented.

Rule (a): If $\ell_{i}$ appears $q=q(\ell_{i})\geq 0$ times in the clauses and
is linked in $G_{VC}$ to $t_{1},\ldots,t_{q}$ where the $t$’s belong to the
triangles $T_{j}$ and follow the order ${\cal O}_{T}$, then we create the arcs
$((\ell_{i},\ell_{i}\overline{\ell}_{i},6),(\ell_{i},\ell_{i}t_{1},1))$,
$((\ell_{i},\ell_{i}t_{1},6),(\ell_{i},\ell_{i}t_{2},1))$, $\ldots$,
$((\ell_{i},\ell_{i}t_{q-1},6),(\ell_{i},\ell_{i}t_{q},1))$.

Rule (b): We consider the triangular sets of edges $E^{\prime}_{j}$ described
in the construction of $G_{VC}$.

$\bullet$ If $\ell_{i}$ does not belong to any such edge, we create the arc
$((\ell_{i},\ell_{i}t_{q},6),\alpha_{i+1})$ —or
$((\ell_{i},\ell_{i}\overline{\ell}_{i},6),\alpha_{i+1})$ if $\ell_{i}$ does
not apppear in any clause— unless $i=n$, in which case we create
$((\ell_{i},\ell_{i}t_{q},6),\beta_{1})$ or
$((\ell_{i},\ell_{i}\overline{\ell}_{i},6),\beta_{1})$, where $\beta_{1}$ is a
new vertex that will be spoken of at the beginning of Step 3.

$\bullet$ If $\ell_{i}$ belongs to $s=s(\ell_{i})>0$ edges from
$E^{\prime}_{j}$, which link $\ell_{i}$ to $s$ literals
$\ell_{i_{1}},\ldots,\ell_{i_{s}}$ that follow the order ${\cal O}_{\ell}$,
then we build the arc
$((\ell_{i},\ell_{i}t_{q},6),(\ell_{i},\ell_{i}\ell_{i_{1}},1))$ —or the arc
$((\ell_{i},\ell_{i}\overline{\ell}_{i},6),(\ell_{i},\ell_{i}\ell_{i_{1}},1))$
if $q=0$; next, the arcs $((\ell_{i},\ell_{i}\ell_{i_{1}},6),(\ell_{i},$
$\ell_{i}\ell_{i_{2}},1))$, $\ldots$,
$((\ell_{i},\ell_{i}\ell_{i_{s-1}},6),(\ell_{i},\ell_{i}\ell_{i_{s}},1))$ and
$((\ell_{i},\ell_{i}\ell_{i_{s}},6),\alpha_{i+1})$, unless $i=n$, in which
case we create $((\ell_{i},\ell_{i}\ell_{i_{s}},6),\beta_{1})$.

###### Remark 16

In the example of Figure 7, one can see that if a path takes, e.g., the arc
$(\alpha_{1},(x_{1},x_{1}\overline{x}_{1},1))$, then it visits the vertices
$(x_{1},x_{1}\overline{x}_{1},6)$, $(x_{1},x_{1}a_{1},1)$,
$(x_{1},x_{1}a_{1},6)$, and $\alpha_{2}$. If on the other hand, we use the arc
$(\alpha_{1},(\overline{x}_{1},x_{1}\overline{x}_{1},1))$, we also go to
$\alpha_{2}$. The same is true between $\alpha_{2}$ and $\alpha_{3}$,
$\ldots$, between $\alpha_{n-1}$ and $\alpha_{n}$, between $\alpha_{n}$ and
$\beta_{1}$.

We can see that so far, $\alpha_{1}$ has (out-)degree 2, $\alpha_{2}$,
$\ldots$, $\alpha_{n}$ have degree 4 (in- and out-degrees equal to 2), and
$\beta_{1}$ has (in-)degree 2.

Step 3. We consider the $m$ clauses and the $m$ corresponding triangles
$T_{j}$.

We create $2m$ vertices $\beta_{j},\beta^{\prime}_{j}$, $1\leq j\leq m$. As we
have seen in the previous step, $\beta_{1}$ has already two in-neighbours,
which can be $(\ell_{n},\ell_{n}t_{q},6)$, or
$(\ell_{n},\ell_{n}{\overline{\ell}}_{n},6)$, or
$(\ell_{n},\ell_{n}\ell_{n_{s}},6)$. We also create one more vertex $\delta$,
which will have only in-neighbours, so that $\alpha_{1}$ and $\delta$ will
necessarily be the ends of any directed Hamiltonian path, if such a path
exists.

Now for the triangle $T_{j}=\\{a_{j},b_{j},d_{j}\\}$, $1\leq j\leq m$,
associated to the clause $c_{j}=\\{\ell_{j_{1}},\ell_{j_{2}},\ell_{j_{3}}\\}$
in the graph $G_{VC}$, we consider the six corresponding components
$H_{a_{j}b_{j}}$, $H_{a_{j}d_{j}}$, $H_{b_{j}d_{j}}$, $H_{a_{j}\ell_{j_{1}}}$,
$H_{b_{j}\ell_{j_{2}}}$ and $H_{d_{j}\ell_{j_{3}}}$. The vertices $\beta_{j}$
and $\beta^{\prime}_{j}$ can be seen as triangle selectors, intended to choose
two vertices among three. With this in mind, we create the following arcs (see
Figure 8), for $j\in\\{1,2,\ldots,m\\}$:

Figure 8: The treatment of the triangle $T_{1}$ from Figure 4 (Step 3). The
arrows inside $H_{e}$ are not represented.

Rule (a): $(\beta_{j},(a_{j},a_{j}b_{j},1))$,
$((a_{j},a_{j}b_{j},6),(a_{j},a_{j}d_{j},1))$,
$((a_{j},a_{j}d_{j},6),(a_{j},a_{j}\ell_{j_{1}},$ $1))$,
$((a_{j},a_{j}\ell_{j_{1}},6),\beta^{\prime}_{j})$.

Rule (b): $(\beta_{j},(b_{j},a_{j}b_{j},1))$,
$(\beta^{\prime}_{j},(b_{j},a_{j}b_{j},1))$,
$((b_{j},a_{j}b_{j},6),(b_{j},b_{j}d_{j},1))$, $((b_{j},$
$b_{j}d_{j},6),(b_{j},b_{j}\ell_{j_{2}},1))$,
$((b_{j},b_{j}\ell_{j_{2}},6),\beta^{\prime}_{j})$, plus the arc
$((b_{j},b_{j}\ell_{j_{2}},6),\beta_{j+1})$, unless $j=m$, in which case it is
$((b_{j},b_{j}\ell_{j_{2}},6),\delta)$.

Rule (c): $(\beta^{\prime}_{j},(d_{j},a_{j}d_{j},1))$,
$((d_{j},a_{j}d_{j},6),(d_{j},b_{j}d_{j},1))$,
$((d_{j},b_{j}d_{j},6),(d_{j},d_{j}\ell_{j_{3}},$ $1))$,
$((d_{j},d_{j}\ell_{j_{3}},6),\beta_{j+1})$, unless $j=m$, in which case it is
$((d_{j},d_{j}\ell_{j_{3}},6),\delta)$.

###### Remark 17

In the example of Figure 8, there are three ways for going from $\beta_{1}$ to
$\beta_{2}$ through the components $H_{a_{1}b_{1}}$, $H_{a_{1}d_{1}}$ and
$H_{d_{1}b_{1}}$.

$\bullet$ If a path starts by taking the arc
$(\beta_{1},(a_{1},a_{1}b_{1},1))$, then there are two possibilities,
according to how we visit $H_{a_{1}b_{1}}$:

$\circ$ The first possibility corresponds to taking $a_{1}$ and $d_{1}$, not
$b_{1}$, in a vertex cover: the path completely visits the component
$H_{a_{1}b_{1}}$ from the $a_{1}$-side, then the component $H_{a_{1}d_{1}}$ in
parallel, then the component $H_{a_{1}x_{1}}$ in a so far unspecified way,
then $\beta_{1}^{\prime}$.

Next, it takes the arc $(\beta^{\prime}_{1},(d_{1},d_{1}a_{1},1))$, re-visits
$H_{d_{1}a_{1}}$ in parallel, completely visits $H_{d_{1}b_{1}}$ from the
$d_{1}$-side, then $H_{d_{1}x_{3}}$, and ends this path section at
$\beta_{2}$. One can see that the three components corresponding to edges
incident to $b_{1}$ must all be completely visited from the side opposite
$b_{1}$, including the $x_{2}$-side.

$\circ$ The second possibility corresponds to taking $a_{1}$ and $b_{1}$, not
$d_{1}$, in a vertex cover: the path follows the arc
$(\beta_{1},(a_{1},a_{1}b_{1},1))$, visits $H_{a_{1}b_{1}}$ in parallel,
visits completely $H_{a_{1}d_{1}}$ from the $a_{1}$-side, then
$H_{a_{1}x_{1}}$, and $\beta_{1}^{\prime}$.

Next, it takes the arc $(\beta^{\prime}_{1},(b_{1},b_{1}a_{1},1))$, goes
through $H_{b_{1}a_{1}}$ in parallel, goes completely through $H_{b_{1}d_{1}}$
from the $b_{1}$-side, then $H_{b_{1}x_{2}}$, and ends this path section at
$\beta_{2}$. The component $H_{d_{1}x_{3}}$ is not yet visited.

$\bullet$ Alternatively, a path can start by taking the arc
$(\beta_{1},(b_{1},a_{1}b_{1},1))$; this corresponds to taking $b_{1}$ and
$d_{1}$, not $a_{1}$, in a vertex cover and constitutes the third way for
going from $\beta_{1}$ to $\beta_{2}$. The path then completely visits
$H_{b_{1}a_{1}}$ from the $b_{1}$-side, $H_{b_{1}d_{1}}$ in parallel,
$H_{b_{1}x_{2}}$, and $\beta^{\prime}_{1}$.

Next, it completely visits $H_{d_{1}a_{1}}$ from the $d_{1}$-side,
$H_{d_{1}b_{1}}$ in parallel, $H_{d_{1}x_{3}}$, and this path section ends at
$\beta_{2}$. The component $H_{a_{1}x_{1}}$ is not yet visited.

It is easy to see that these are the only three ways for going from
$\beta_{1}$ to $\beta_{2}$ through the components $H_{a_{1}b_{1}}$,
$H_{a_{1}d_{1}}$ and $H_{d_{1}b_{1}}$, not taking into account the ways of
going through the components $H_{a_{1}x_{1}}$, $H_{b_{1}x_{2}}$ and
$H_{d_{1}x_{3}}$ (this issue will be treated later on, in the general case):
indeed, the only possibility left would be to follow the arc
$(\beta_{1},(b_{1},a_{1}b_{1},1))$ and visit $H_{b_{1}a_{1}}$ in parallel, but
then the $a_{1}$-side of $H_{b_{1}a_{1}}$ cannot be reached.

The same will be true for the components $H_{a_{j}b_{j}}$, $H_{a_{j}d_{j}}$
and $H_{d_{j}b_{j}}$ and the corresponding triangles $T_{j}$, $1\leq j\leq m$,
between $\beta_{j}$ and $\beta_{j+1}$ (or between $\beta_{m}$ and $\delta$).

The description of the oriented graph $H$ is complete. Now $\beta_{1}$ has
increased its degree to 4, and $\beta_{2}$, $\ldots$, $\beta_{m}$ and
$\beta^{\prime}_{1}$, $\ldots$, $\beta^{\prime}_{m}$ have degree 4. Actually,
all the selectors but $\alpha_{1}$ have in-degree 2 and out-degree 2 in $H$.
These $n$ selectors $\alpha_{i}$, $1\leq i\leq n$, and $2m$ selectors
$\beta_{j}$, $\beta_{j}^{\prime}$, $1\leq j\leq m$, translate the choices we
have to make when constructing a vertex cover with size $2m+n$: we have one
choice among the $n$ variables (take $x_{i}$ or ${\overline{x}}_{i}$); as for
the $m$ triangles $T_{j}$ associated to the clauses, Remark 17 has shown how
the selectors $\beta_{j}$, $\beta_{j}^{\prime}$, $1\leq j\leq m$, can be used
to choose two vertices among three. The number of selectors is one reason why
there is no directed Hamiltonian path in $H$ when the vertex covers in
$G_{VC}$ have size at least $2m+n+1$.

The order of $H$ is $12|E_{VC}|+n+2m+1$, which is at most $12(n+9m)+n+2m+1$,
so that the transformation is polynomial indeed.

We are now going to prove our claims about the existence or non-existence,
uniqueness or non-uniqueness, of a directed Hamiltonian path in $H$.

C) How it Works
Assume first that there is an assignment satisfying the instance of U-1-3-SAT,
and therefore that there is a vertex cover $V^{*}$ in $G_{VC}$ with size
$2m+n$. We construct a path in $H$ in a straightforward way: every component
$H_{uv}$ ($uv\in E_{VC}$) with $\\{u,v\\}\subset V^{*}$ is visited in
parallel, whereas $H_{uv}$ is completely visited from the $u$-side whenever
$u\in V^{*}$, $v\notin V^{*}$. Let us have a closer look at how this works:

We start at $\alpha_{1}$, and visit completely the component
$H_{x_{1}{\overline{x}}_{1}}$ from the $x_{1}$-side if $x_{1}=\,$T, from the
${\overline{x}}_{1}$-side if $x_{1}=\,$F (or, equivalently, if $x_{1}\in
V^{*}$ or ${\overline{x}}_{1}\in V^{*}$, respectively). If, say, $x_{1}=\,$F,
we then completely go through all the components corresponding to triangles
$T_{j}$ and involving ${\overline{x}}_{1}$, all from the
${\overline{x}}_{1}$-side; note that all the components just completely
visited involve ${\overline{x}}_{1}$ and a vertex not in $V^{*}$, by the very
construction of the vertex cover $V^{*}$, which is possible because it stems
from an assignment 1-3-satisfying all the clauses. Then we go through the
components constructed from the edge sets $E^{\prime}_{j}$ and involving
${\overline{x}}_{1}$; those involving a second vertex in $V^{*}$ (i.e., a true
literal) are visited in parallel, whereas those involving a vertex not in
$V^{*}$ are completely visited from the ${\overline{x}}_{1}$-side; then the
path arrives at $\alpha_{2}$. The components involving $x_{1}$, apart from
$H_{x_{1}{\overline{x}}_{1}}$, remain completely unvisited for the time being,
and the components that have been visited in parallel will have to be re-
visited.

We act similarly between $\alpha_{2}$ and $\alpha_{3}$, $\ldots$, $\alpha_{n}$
and $\beta_{1}$; cf. Remark 16. When doing this, we re-visit all the
components that had been visited only in parallel, and completely visit the
components involving a literal not in $V^{*}$ and corresponding to edges in
$E^{\prime}_{j}$. The only components not visited yet between $\alpha_{1}$ and
$\beta_{1}$ are those corresponding to edges between a false literal (not in
$V^{*}$) and its neighbours in the triangles $T_{j}$.

Next, starting from $\beta_{1}$, we use Remark 17 according to the three
possible cases: (a) $\\{a_{1},d_{1}\\}\subset V^{*},$ $b_{1}\notin V^{*}$, (b)
$\\{a_{1},b_{1}\\}\subset V^{*},$ $d_{1}\notin V^{*}$, (c)
$\\{b_{1},d_{1}\\}\subset V^{*},$ $a_{1}\notin V^{*}$. We give in detail only
the third case, for the clause $c_{1}=\\{\ell_{1},\ell_{2},\ell_{3}\\}$: we
use the arc $(\beta_{1},(b_{1},a_{1}b_{1},1))$ and completely visit the
component $H_{a_{1}b_{1}}$ from the $b_{1}$-side, then the component
$H_{b_{1}d_{1}}$ in parallel, then the complete component $H_{b_{1}\ell_{2}}$
from the $b_{1}$-side (because if $b_{1}\in V^{*}$, then $\ell_{2}\notin
V^{*}$ and this component had not yet been visited) and end at
$\beta^{\prime}_{1}$. Next, we take the arc
$(\beta^{\prime}_{1},(d_{1},d_{1}a_{1},1))$, we completely visit
$H_{d_{1}a_{1}}$ from the $d_{1}$-side, re-visit $H_{d_{1}b_{1}}$ in parallel,
completely visit $H_{d_{1}\ell_{3}}$ from the $d_{1}$-side, and this path
section ends at $\beta_{2}$. Note that (a) the three components involving
$a_{1}$ between $\beta_{1}$ and $\beta_{2}$ have been completely visited, from
the $b_{1}$-, $d_{1}$\- or $\ell_{1}$-sides (because $a_{1}\notin V^{*}$
implies that $\ell_{1}\in V^{*}$); (b) any so far unvisited component
involving a false literal (here, these are $\ell_{2}$ and $\ell_{3}$) and one
of the vertices of the triangle $T_{1}$ (here $b_{1}$ and $d_{1}$) has now
been completely visited from the triangle sides (here from the $b_{1}$\- and
$d_{1}$-sides).

We act similarly between $\beta_{2}$ and $\beta_{3}$, $\ldots$, $\beta_{m}$
and $\delta$; cf. the end of Remark 17. The ultimate section takes us between
$\beta_{m}$ and $\delta$, the final vertex, and we have indeed built a
directed Hamiltonian path, from $\alpha_{1}$ to $\delta$, in the oriented
graph $H$.

Obviously, two different assignments 1-3-satisfying all the clauses lead,
following the above process, to two different paths in $H$. We still want to
prove that 1) if no assignment 1-3-satisfying all the clauses exists, then no
path exists, and 2) a unique assignment 1-3-satisfying all the clauses leads
to a unique path.

1) We assume that there is a directed Hamiltonian path ${\cal HP}$ in $H$, and
exhibit an assignment 1-3-satisfying all the clauses.

Let us consider the vertex $\alpha_{1}$; its two out-neighbours in $H$ are
$(x_{1},x_{1}\overline{x}_{1},1)$ and
$(\overline{x}_{1},x_{1}\overline{x}_{1},1)$. So exactly one of the arcs
$(\alpha_{1},(x_{1},x_{1}\overline{x}_{1},1))$,
$(\alpha_{1},(\overline{x}_{1},x_{1}\overline{x}_{1},1))$ is part of ${\cal
HP}$. The same is true for $\alpha_{i}$, $1<i\leq n$. As a consequence, we can
define a valid assignment of the variables $x_{i}$, $1\leq i\leq n$, by
setting $x_{i}=\,$T if and only if the arc
$(\alpha_{i},(x_{i},x_{i}\overline{x}_{i},1))$ belongs to ${\cal HP}$.

Next, we address the vertices $\beta_{j}$, $1\leq j\leq m$. The construction
in Steps 2 and 3 is such that each vertex $\beta_{j}$, $1\leq j\leq m$, has
two out-neighbours, $(a_{j},a_{j}b_{j},1)$ and $(b_{j},a_{j}b_{j},1)$.

This implies that the assignment defined above is such that there is at least
one true literal in each clause. Indeed, if we assume that the clause
$c_{j}=\\{\ell_{j_{1}},\ell_{j_{2}},\ell_{j_{3}}\\}$ does not contain any true
literal, then the component $H_{a_{j}\ell_{j_{1}}}$ is completely visited by
${\cal HP}$ from the $a_{j}$-side, because $\ell_{j_{1}}=\,$F implies that the
arc $(\alpha_{j},(\ell_{j_{1}},\ell_{j_{1}}{\overline{\ell}}_{j_{1}},1))$ is
not part of ${\cal HP}$ and does not give access to the $\ell_{j_{1}}$-side.
Similarly, the components $H_{b_{j}\ell_{j_{2}}}$ and $H_{d_{j}\ell_{j_{3}}}$
are completely visited by ${\cal HP}$ from the $b_{j}$\- and $d_{j}$-sides,
respectively. This in turn implies that in ${\cal HP}$ we have the arcs
$((a_{j},a_{j}\ell_{j_{1}},6),\beta^{\prime}_{j})$,
$(\beta_{j},(a_{j},a_{j}b_{j},1))$,
$((d_{j},d_{j}\ell_{j_{3}},6),\beta_{j+1})$ and
$(\beta^{\prime}_{j},(d_{j},d_{j}a_{j},1))$ —replace $\beta_{j+1}$ by $\delta$
if $j=m$. Now how does ${\cal HP}$ go through $(b_{j},b_{j}\ell_{j_{2}},6)$?
It cannot be with the help of the $\ell_{j_{2}}$-side of
$H_{b_{j}\ell_{j_{2}}}$, so there are only two possibilities left: but if it
is with the arc $((b_{j},b_{j}\ell_{j_{2}},6),\beta^{\prime}_{j})$, then
$\beta^{\prime}_{j}$ has three neighbours in ${\cal HP}$, which is impossible;
and if it is with the arc $((b_{j},b_{j}\ell_{j_{2}},6),\beta_{j+1})$, then in
${\cal HP}$, the vertex $\beta_{j+1}$ has two in-neighbours, which is
impossible —including when $j=m$ and $\beta_{j+1}$ is replaced by $\delta$.
From this we can conclude that the clause
$c_{j}=\\{\ell_{j_{1}},\ell_{j_{2}},\ell_{j_{3}}\\}$ contains at least one
true literal.

Assume next that one clause has at least two true literals: without loss of
generality, $c_{j}=\\{\ell_{j_{1}},\ell_{j_{2}},\ell_{j_{3}}\\}$ is such that
$\ell_{j_{1}}=\ell_{j_{2}}=\,$T. Then ${\cal HP}$ has no access to the
${\overline{\ell}}_{j_{1}}$\- and ${\overline{\ell}}_{j_{2}}$\- sides of the
components involving ${\overline{\ell}}_{j_{1}}$ or
${\overline{\ell}}_{j_{2}}$, but, since there is the edge
${\overline{\ell}}_{j_{1}}{\overline{\ell}}_{j_{2}}$ in $G_{VC}$, this means
that ${\cal HP}$ has no way of visiting the component
$H_{{\overline{\ell}}_{j_{1}}{\overline{\ell}}_{j_{2}}}$. Therefore, we have
just established that the assignment derived from the path ${\cal HP}$
1-3-satisfies all the clauses. This, together with the fact that two
assignments 1-3-satisfying the clauses lead to two paths, shows that a NO
answer to the instance of U-1-3-SAT implies a NO answer for the constructed
instance $H$ of U-HAMP[O].

2) We want to show that a unique assignment ${\cal A}$ 1-3-satisfying all the
clauses leads to a unique path in $H$. This assignment leads to a unique
vertex cover $V^{*}$, of size $n+2m$, in $G_{VC}$, and to a path in $H$, as
already seen. Now assume that we have a second path, so that these two paths,
which we call ${\cal HP}_{1}$ and ${\cal HP}_{2}$, both lead, with the above
description in 1), to the same ${\cal A}$ and the same $V^{*}$.

The two paths must behave in the same way over the components
$H_{x_{i}{\overline{x}}_{i}}$, $1\leq i\leq n$: otherwise, from them we could
define two different valid assignments, which would both, as seen previously,
1-3-satisfy the clauses.

Next, consider the clause $c_{j}=\\{\ell_{j_{1}},\ell_{j_{2}},\ell_{j_{3}}\\}$
and assume without loss of generality that ${\cal A}(\ell_{j_{1}})=\,$T,
${\cal A}(\ell_{j_{2}})={\cal A}(\ell_{j_{3}})=\,$F; this implies, for both
${\cal HP}_{1}$ and ${\cal HP}_{2}$, that the components
$H_{\ell_{j_{1}}{\overline{\ell}}_{j_{1}}}$,
$H_{\ell_{j_{2}}{\overline{\ell}}_{j_{2}}}$ and
$H_{\ell_{j_{3}}{\overline{\ell}}_{j_{3}}}$ are completely visited from the
$\ell_{j_{1}}$-, ${\overline{\ell}}_{j_{2}}$\- and
${\overline{\ell}}_{j_{3}}$-sides, respectively, so that both paths have no
access to the $\ell_{j_{2}}$\- nor $\ell_{j_{3}}$-sides. As a consequence,
between $\beta_{j}$ and $\beta_{j+1}$ (or $\beta_{m}$ and $\delta$), the
components $H_{b_{j}\ell_{j_{2}}}$ and $H_{d_{j}\ell_{j_{3}}}$ are completely
visited from the $b_{j}$\- and $d_{j}$-sides, respectively. Then necessarily
the following arcs belong to ${\cal HP}_{1}$ and ${\cal HP}_{2}$, going along
the $d_{j}$-side:

$((d_{j},d_{j}\ell_{j_{3}},6),\beta_{j+1})$ —or
$((d_{j},d_{j}\ell_{j_{3}},6),\delta)$—,
$((d_{j},d_{j}b_{j},6),(d_{j},d_{j}\ell_{j_{3}},1))$, $((d_{j},d_{j}a_{j},$
$6),(d_{j},d_{j}b_{j},1))$, $(\beta^{\prime}_{j},(d_{j},d_{j}a_{j},1))$;

and going along the $b_{j}$-side:

$((b_{j},b_{j}\ell_{j_{2}},6),\beta^{\prime}_{j})$ (because $\beta_{j+1}$ —or
$\delta$— cannot have two in-neighbours), and
$((b_{j},b_{j}d_{j},6),(b_{j},b_{j}\ell_{j_{2}},1))$,
$((b_{j},b_{j}a_{j},6),(b_{j},b_{j}d_{j},1))$.

The component $H_{b_{j}d_{j}}$ must be visited in parallel, and it is
$(\beta_{j},(b_{j},b_{j}a_{j},1))$ that belongs to the two paths.

We can see that all the components containing $a_{j}$, in particular
$H_{a_{j}\ell_{j_{1}}}$, must be completely visited from the sides opposite
$a_{j}$. So far, we have proved that the two paths ${\cal HP}_{1}$ and ${\cal
HP}_{2}$ behave identically between $\beta_{j}$ and $\beta_{j+1}$ (or
$\beta_{m}$ and $\delta$), including on the components corresponding to
membership edges (between literals and triangles).

Consider now what happens between $\alpha_{i}$ and $\alpha_{i+1}$ (or
$\alpha_{n}$ and $\beta_{1}$). Assume without loss of generality that, say,
${\cal A}(x_{i})=\,$T, so that
$(\alpha_{i},(x_{i},x_{i}{\overline{x}}_{i},1))$ is part of the two paths.
Consider the components involving $x_{i}$ in $H$: there are first those
involving vertices of type $a$, $b$ or $d$, which translate the membership of
$x_{i}$ to a certain number of clauses, and which we called
$t_{1},\ldots,t_{q}$ in Step 2(a); we have already seen in the previous
paragraph that these components must be completely visited from the
$x_{i}$-side.

Then we consider the components created from the edges in $E^{\prime}_{j}$,
cf. Step 2(b); here, some edges in $G_{VC}$ can have both ends in $V^{*}$,
but, using similar arguments as before, we can see that the two paths will
visit all these components in the same way: consider the clause
$c_{j}=\\{\ell_{j_{1}},\ell_{j_{2}},\ell_{j_{3}}\\}$ and the corresponding set
$E^{\prime}_{j}$, and assume without loss of generality that
$x_{i}=\ell_{j_{1}}$, so that ${\cal A}(\ell_{j_{1}})=\,$T, which implies that
${\cal A}(\ell_{j_{2}})={\cal A}(\ell_{j_{3}})=\,$F; then
$H_{{\overline{\ell}}_{j_{1}}{\overline{\ell}}_{j_{2}}}$ and
$H_{{\overline{\ell}}_{j_{1}}{\overline{\ell}}_{j_{3}}}$ must be completely
visited from the ${\overline{\ell}}_{j_{2}}$\- and
${\overline{\ell}}_{j_{3}}$-sides, respectively, and
$H_{{\overline{\ell}}_{j_{2}}{\overline{\ell}}_{j_{3}}}$ in parallel, i.e.,
the two paths have no choice but to behave identically on all three
components. As for the components with ${\overline{x}}_{i}$, they must be
completely visited from the side which is not the side of
${\overline{x}}_{i}$.

So we have just proved that the two paths are identical between $\alpha_{1}$
and $\alpha_{2}$, $\ldots$, $\alpha_{n}$ and $\beta_{1}$.

Therefore, the two paths (between $\alpha_{1}$ and $\delta$) are one and the
same. $\Diamond$

## References

  * [1] J.-P. BARTHÉLEMY, G. D. COHEN and A. C. LOBSTEIN: Algorithmic Complexity and Communication Problems, London: University College of London, 1996.
  * [2] A. BLASS and Y. GUREVICH: On the unique satisfiability problem, Information and Control, Vol. 55, pp. 80-88, 1982.
  * [3] C. CALABRO, R. IMPAGLIAZZO, V. KABANETS and R. PATURI: The complexity of Unique $k$-SAT: an isolation lemma for $k$-CNFs, Journal of Computer and System Sciences, Vol. 74, pp. 386–393, 2008.
  * [4] S. A. COOK: The complexity of theorem-proving procedures, Proceedings of 3rd Annual ACM Symposium on Theory of Computing, pp. 151–158, 1971.
  * [5] T. CORMEN: Algorithmic complexity, in: K. H. Rosen (ed.) Handbook of Discrete and Combinatorial Mathematics, pp. 1077–1085, Boca Raton: CRC Press, 2000.
  * [6] M. R. GAREY and D. S. JOHNSON: Computers and Intractability, a Guide to the Theory of NP-Completeness, New York: Freeman, 1979.
  * [7] L. HEMASPAANDRA: Complexity classes, in: K. H. Rosen (ed.) Handbook of Discrete and Combinatorial Mathematics, pp. 1085–1090, Boca Raton: CRC Press, 2000.
  * [8] O. HUDRY and A. LOBSTEIN: Complexity of unique (optimal) solutions in graphs: Vertex Cover and Domination, Journal of Combinatorial Mathematics and Combinatorial Computing, Vol. 110, pp. 217-240, 2019.

  * [9] O. HUDRY and A. LOBSTEIN: Unique (optimal) solutions: complexity results for identifying and locating-dominating codes, Theoretical Computer Science, Vol. 767, pp. 83-102, 2019.
  * [10] O. HUDRY and A. LOBSTEIN: Some Complexity Considerations on the Uniqueness of Solutions for Colouring and Satisfiability Problems, submitted.
  * [11] D. S. JOHNSON: A catalog of complexity classes, in: Handbook of Theoretical Computer Science, Vol. A: Algorithms and Complexity, van Leeuwen, Ed., Chapter 2, Elsevier, 1990.
  * [12] R. M. KARP: Reducibility among combinatorial problems, in: R. E. Miller and J. W. Thatcher (eds.) Complexity of Computer Computations, pp. 85–103, New York: Plenum Press, 1972.
  * [13] C. H. PAPADIMITRIOU: On the complexity of unique solutions, Journal of the Association for Computing Machinery, Vol. 31, pp. 392-400, 1984.
  * [14] C. H. PAPADIMITRIOU: Computational Complexity, Reading: Addison-Wesley, 1994.
  * [15] C. H. PAPADIMITRIOU and M. YANNAKAKIS: The complexity of facets (and some facets of complexity), Journal of Computer and System Sciences, Vol. 28, pp. 244–259, 1984.
  * [16] T. J. SCHAEFER: The complexity of satisfiability problems, Proceedings of 10th Annual ACM Symposium on Theory of Computing, pp. 216–226, 1978.
  * [17] https://complexityzoo.uwaterloo.ca/Complexity Zoo