On the Complexity of the Uniqueness of Solutions in Graph Problems
Rapport interne Telecom ParisTech-2017D001, Paris, France, 119 pages, avril 2017.
Olivier HUDRY (#) & Antoine LOBSTEIN (*)
(#) Département Informatique et Réseaux, LTCI,
Télécom ParisTech, Université Paris-Saclay,
46 rue Barrault, 75634 Paris Cedex 13 - France
olivier.hudry@telecom-paristech.fr
(*) Centre National de la Recherche Scientifique,
Laboratoire de Recherche en Informatique, UMR 8623,
Université Paris-Sud, Université Paris-Saclay,
Bâtiment 650 Ada Lovelace, 91405 Orsay Cedex - France
antoine.lobstein@lri.fr
Abstract. This Report contains four articles submitted(+), to appear(+) or published(+) to international journals of mathematics with reviewing process, all about the same general topic, namely, the study of the complexity of problems dealing with the uniqueness of a solution, for classical problems in complexity theory, either Boolean satisfiability problems, or graph problems. More specifically:
the first article(+) deals with the satisfiability problems SAT, k-SAT, k > 1, and 1-3-SAT, as well as the problem of the existence of colourings in a given graph (Sections 1-4 in this Report);
the second article(+) deals with the vertex cover problem and the dominating set (or code) problem in a given graph (Sections 5-8);
the third article(+) deals with the locating-dominating and the identifying problems, in a given graph (Sections 9-13);
the fourth and last article(+) deals with the problem of finding Hamiltonian cycles or paths in a directed, oriented or undirected given graph (Sections 14-16).
We try to locate accurately these problems inside the classes of complexity, and to establish equivalences between problems, in particular by constructing polynomial reductions from one problem to another.
(+) The first article is still submitted. The second article appeared in Journal of Combinatorial Mathematics and Combinatorial Computing (Vol. 110, pp. 217-240, 2019). The third article appeared in Theoretical Computer Science (Vol. 767, pp. 83-102, 2019.). The fourth article is to appear in Journal of Combinatorial Mathematics and Combinatorial Computing.