Olivier Hudry Ltci

Antoine Lobstein
email: antoine.lobstein@lri.fr

Unique (Optimal) Solutions: Complexity Results for Identifying and Locating-Dominating Codes

Keywords: Complexity Theory, Graph Theory, Uniqueness of Solution, Polynomial Reduction, Locating-Dominating Codes, Identifying Codes 1

HAL is

Introduction

We intend to locate in the classes of complexity some problems dealing with the existence of a unique identifying or locating-dominating code in a given graph.

Uniqueness of solutions has been studied in a few papers (see, e.g., [START_REF] Blass | On the unique satisfiability problem[END_REF], [START_REF] Blidia | Characterizations of trees with unique minimum locating-dominating sets[END_REF], [START_REF] Calabro | The complexity of Unique k-SAT: an isolation lemma for k-CNFs[END_REF], [START_REF] Fischermann | Block graphs with unique minimum dominating sets[END_REF], [START_REF] Gunther | Graphs with unique minimum dominating sets[END_REF], [START_REF] Papadimitriou | On the complexity of unique solutions[END_REF]) and may be seen as part of the wider and unexplored issue of the number of solutions of a problem.

Identifying and Locating-Dominating Codes

For graph theory, we refer to, e.g., [START_REF] Berge | English translation: Graphs[END_REF] or [START_REF] Diestel | Graph Theory[END_REF].

For identification in graphs, see the seminal paper [START_REF] Karpovsky | On a new class of codes for identifying vertices in graphs[END_REF]; for locatingdominating codes, see the first papers [START_REF] Colbourn | Locating dominating sets in series parallel networks[END_REF] and [START_REF] Slater | Domination and location in graphs[END_REF]. For both, see also the large bibliography at [START_REF] Lobstein | Watching systems, identifying, locating-dominating and discriminating codes in graphs[END_REF], where almost 400 references show that these topics are burgeoning.

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 ∈ V and y ∈ V is indifferently denoted by xy or yx. The order of the graph is its number of vertices, |V |.

A path P k = x 1 x 2 . . . x k is a sequence of k distinct vertices x i , 1 ≤ i ≤ k, such that x i x i+1 is an edge for i ∈ {1, 2, . . . , k -1}. The length of P k is its number of edges, k -1. A cycle C k = x 1 x 2 . . . x k is a sequence of k distinct vertices x i , 1 ≤ i ≤ k, where x i x i+1 is an edge for i ∈ {1, 2, . . . , k -1}, and x k x 1 is also an edge; its length is k.

In a connected graph G, we can define the distance between any two vertices x and y, denoted by d G (x, y), as the length of any shortest path between x and y. This definition can be extended to disconnected graphs, using the convention that d G (x, y) = +∞ if no path exists between x and y. The subscript G can be dropped when there is no ambiguity.

For an integer k ≥ 2, the k-th transitive closure, or k-th power of G = (V, E) is the graph

G k = (V, E k ) defined by E k = {uv : u ∈ V, v ∈ V, d G (u, v) ≤ k}.
For any vertex v ∈ V , the open neighbourhood N (v) of v consists of the set of vertices adjacent to v, i.e., N (v) = {u ∈ V : uv ∈ E}; the closed neighbourhood of v is B 1 (v) = N (v) ∪ {v}. This notation can be generalized to any integer r ≥ 0 by setting

B r (v) = {x ∈ V : d(x, v) ≤ r}.
For X ⊆ V ,we denote by B r (X) the set of vertices within distance r from X: B r (X) = ∪ x∈X B r (x).

Two vertices x and y such that B r (x) = B r (y), x = y, are called r-twins. If G has no r-twins, we say that G is r-twin-free. Whenever two vertices

x and y are such that x ∈ B r (y) (which is equivalent to y ∈ B r (x)), we say that x and y r-cover or r-dominate each other; note that every vertex r-dominates itself. A set W is said to r-dominate a set Z if every vertex in Z is r-dominated by at least one vertex of W , or equivalently: Z ⊆ B r (W ). When three vertices x, y, z are such that x ∈ B r (z) and y / ∈ B r (z), we say that z r-separates x and y in G (note that z = x is possible). A set of vertices is said to r-separate x and y if it contains at least one vertex which does.

A code C is simply a subset of V , and its elements are called codewords.

We say that C is an r-identifying code [START_REF] Karpovsky | On a new class of codes for identifying vertices in graphs[END_REF] if all the sets B r (v) ∩ C, v ∈ V , are nonempty and distinct: in other words, every vertex is r-covered by C, and every pair of vertices is r-separated by C. It is quite easy to observe that a graph G admits an r-identifying code if and only if G is r-twin-free; this is why r-twin-free graphs are also called r-identifiable. When G is r-twin-free, we denote by i r (G) the smallest cardinality of an r-identifying code in G, and call it the r-identification number of G; any r-identifying code C such that |C| = i r (G) is said to be optimal.

We say that C is an r-locating-dominating code (r-LD code for short) [START_REF] Slater | Domination and location in graphs[END_REF], [START_REF] Colbourn | Locating dominating sets in series parallel networks[END_REF] if all the sets B r (v) ∩ C, v ∈ V \ C, are nonempty and distinct: in other words, every vertex is r-dominated by C (since a codeword dominates itself), and every pair of non-codewords is r-separated by C. We denote by LD r (G) the smallest cardinality of an r-locating-dominating code in G, and call it the r-location-domination number of G; any r-LD code C such that |C| = LD r (G) is said to be optimal.

For the needs of Theorems 19 and 34, we give the following obvious characterization: a code C is r-identifying (respectively, r-LD) if and only if (a) for every vertex x ∈ V , B r (x) ∩ C = ∅, and (b) for every pair of distinct vertices x i ∈ V , x j ∈ V (respectively, x i ∈ V \ C, x j ∈ V \ C), we have

B r (x i )∆B r (x j ) ∩ C = ∅, (1)
where ∆ stands for the symmetric difference. Note that, when dealing with locating-dominating codes, we shall rather use the word "dominate", whereas for identifying codes, we shall prefer "cover".

It is known that the following two decision problems, stated for any integer r ≥ 1, are NP-complete (see below Propositions 13 from [START_REF] Colbourn | Locating dominating sets in series parallel networks[END_REF], [START_REF] Charon | Minimizing the size of an identifying or locating-dominating code in a graph is NP-hard[END_REF], and 29 from [START_REF] Cohen | On identifying codes[END_REF], [START_REF] Charon | Minimizing the size of an identifying or locating-dominating code in a graph is NP-hard[END_REF]):

Problem LDC r (r-Locating-Dominating Code with bounded size): Instance: A graph G and an integer k. Question: Does G admit an r-locating-dominating code of size at most k? Problem IdC r (r-Identifying Code with bounded size): Instance: An r-twin-free graph G and an integer k. Question: Does G admit an r-identifying code of size at most k?

In this paper, we are interested in the following four problems, which deal with the uniqueness of a solution, and we are going to locate them in the classes of complexity.

Problem U-LDC r (Unique r-Locating-Dominating Code with bounded size): Instance: A graph G and an integer k. Question: Does G admit a unique r-locating-dominating code of size at most k?

Problem U-OLDC r (Unique Optimal r-Locating-Dominating Code): Instance: A graph G. Question: Does G admit a unique optimal r-locating-dominating code?

Problem U-IdC r (Unique r-Identifying Code with bounded size): Instance: An r-twin-free graph G and an integer k. Question: Does G admit a unique r-identifying code of size at most k?

Problem U-OIdC r (Unique Optimal r-Identifying Code): Instance: An r-twin-free graph G. Question: Does G admit a unique optimal r-identifying code?

Our results are the following: we give polynomial reductions from "Unique Satisfiability of a Boolean formula" (U-SAT) to U-OLDC r , as well as from U-SAT to U-OIdC r ; we prove that U-LDC r and U-IdC r have the same complexity as U-SAT, up to polynomials. As a consequence, all these problems are NP-hard, and U-LDC r and U-IdC r belong to the class DP. The problems U-OLDC r and U-OIdC r belong "only" to the class L N P , which contains DP.

In a previous work [START_REF] Hudry | More results on the complexity of identifying problems in graphs[END_REF], we have investigated the complexity of the existence of, and of the search for, optimal r-identifying codes, as well as optimal r-identifying codes containing a given subset of vertices; see also [START_REF] Charon | Minimizing the size of an identifying or locating-dominating code in a graph is NP-hard[END_REF], [START_REF] Cohen | On identifying codes[END_REF]Sec. 5]. In a forthcoming work, we extend the present study on uniqueness issues to Boolean satisfiability and graph colouring [START_REF] Hudry | Some complexity considerations on the uniqueness of solutions for satisfiability and colouring problems[END_REF], Vertex Cover and Dominating Set (as well as its generalization to domination within distance r) [START_REF] Hudry | Complexity of unique (optimal) solutions in graphs: Vertex Cover and Domination[END_REF], and Hamiltonian Cycle [START_REF] Hudry | On the complexity of determining whether there is a unique Hamiltonian cycle in a graph[END_REF]. At the other end, there has been research on how many optimal r-identifying codes can exist in a graph [START_REF] Honkala | On the number of optimal identifying codes in a twin-free graph[END_REF], and on the structure of the ensemble of optimal r-locatingdominating codes [START_REF] Honkala | On the ensemble of optimal dominating and locating-dominating codes in a graph[END_REF] and of optimal r-identifying codes [START_REF] Honkala | On the ensemble of optimal identifying codes in a twin-free graph[END_REF].

For other works in the area of complexity, see, e.g., [START_REF] Auger | Identifying codes in trees and planar graphs[END_REF], [START_REF] Auger | Minimal identifying codes in trees and planar graphs with large girth[END_REF], [START_REF] Auger | Complexity results for identifying codes in planar graphs[END_REF], [START_REF] Foucaud | Aspects combinatoires et algorithmiques des codes identifiants dans les Thèse de Doctorat[END_REF], [START_REF] Foucaud | Identifying codes in line graphs[END_REF], [START_REF] Foucaud | Identification, location-domination and metric dimension on interval and permutation graphs: II. Algorithms and complexity[END_REF], and [START_REF] Parreau | Problèmes d'identification dans les graphes[END_REF], which establish, in particular, polynomiality or NPcompleteness results for the identification problem when restricted to some subclasses of graphs, such as trees, planar graphs, bipartite graphs, interval graphs or line graphs. See also [START_REF] Foucaud | Decision and approximation complexity for identifying codes and locating-dominating sets in restricted graph classes[END_REF], [START_REF] Gravier | Hardness results and approximation algorithms for identifying codes and locating-dominating codes in graphs[END_REF] and [START_REF] Suomela | Approximability of identifying codes and locatingdominating codes[END_REF] for approximation issues for both identifying and locating-dominating codes.

In the sequel, we shall also need the following tools, which constitute classical definitions related to Boolean satisfiability.

We consider a set X of n Boolean variables x i and a set C of m clauses, each clause c j containing κ j literals, a literal being a variable x i or its complement x i . A truth assignment for 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 C if every clause contains at least one true literal. The following decision problem, for which the size of the instance is polynomially linked to n+m, is a classical problem in complexity.

Problem SAT (Satisfiability):

Instance: A set X of variables, a collection C of clauses over X , each clause containing at least two different literals. Question: Is there a truth assignment for X that satisfies C?

We shall also need the variant U-SAT of SAT (see [START_REF] Blass | On the unique satisfiability problem[END_REF], [START_REF] Papadimitriou | The complexity of facets (and some facets of complexity[END_REF]), which has the same instance as SAT but the question now is: "Is there a unique truth assignment. . .?".

We shall give in Proposition 2 what we need to know about the complexity of this problem. We now provide the necessary definitions and notation for complexity.

Necessary Notions in Complexity

We expound here, not too formally, the notions of complexity that will be needed in the sequel. We refer the reader to, e.g., [START_REF] Barthélemy | Algorithmic Complexity and Communication Problems[END_REF], [START_REF] Garey | Computers and Intractability, a Guide to the Theory of NP-Completeness[END_REF], [START_REF] Johnson | A catalog of complexity classes[END_REF] or [START_REF] Papadimitriou | Computational Complexity[END_REF] for more on this topic.

A decision problem is of the type "Given an instance I and a property PR on I, is 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 π 1 to a decision problem π 2 is a polynomial transformation that maps any instance of π 1 into an "equivalent" instance of π 2 , that is, an instance of π 2 admitting the same answer as the instance of π 1 ; in this case, we shall write π 1 → p π 2 . Cook [START_REF] Cook | The complexity of theorem-proving procedures[END_REF] 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-complete or NP-C. The way to show that a decision problem π is NP-complete is, once it is proved to be in NP, to choose some NP-complete problem π 1 and to polynomially reduce it to π. From a practical viewpoint, the NP-completeness of a problem π implies that we do not know any polynomial algorithm solving π, and that, under the assumption P = 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, the size is polynomially linked to its order).

The complement of a decision problem, "Given I and PR, is PR true for I?", is "Given I and PR, is PR false for I?". The class co-NP (respectively, co-NP-complete or co-NP-C) is the class of the problems which are the complement of a problem in NP (respectively, in NP-complete).

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

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

The notions of completeness and hardness can of course be extended to classes other than NP or co-NP. NP-hardness is defined differently in [START_REF] Cormen | Algorithmic complexity[END_REF] and [START_REF] Hemaspaandra | Complexity classes[END_REF]: there, a problem π is NP-hard if there is a polynomial reduction from some NP-complete problem to π; this may lead to confusion (see Section 5).

Finally we introduce the classes P N P (also known as ∆ 2 in the hierarchy of classes) and L N P (also denoted by P N P [O(log n)] or Θ 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 [START_REF] Papadimitriou | The complexity of facets (and some facets of complexity)[END_REF] (or DIF P [1] or BH 2 [START_REF] Johnson | A catalog of complexity classes[END_REF], [START_REF]Complexity Zoo[END_REF], . . .) as the class of languages (or problems) L such that there are two languages L 1 ∈ NP and L 2 ∈ co-NP satisfying L = L 1 ∩ L 2 . This class is not to be confused with NP ∩ co-NP (see the warning in, e.g., [36, p. 412]); actually, DP contains NP ∪ co-NP and is contained in L N P . See Figure 1.

Membership to P, NP, co-NP, DP, L N P or P N P gives an upper bound on the complexity of a problem (this problem is not more difficult than . . .), whereas a hardness result gives a lower bound (this problem is at least as difficult as . . .). Still, such results are conditional in some sense; if for example P=NP, they would lose their interest. But it is not known whether or where the classes of complexity collapse.

The problem SAT is one of the most well-known NP-complete problems [START_REF] Cook | The complexity of theorem-proving procedures[END_REF], [34, p. 39, p. 46 and p. 259]. The following result is easy.

Proposition 2 The problem U-SAT is NP-hard (and co-NP-hard by Remark 1), and belongs to the class DP [START_REF] Papadimitriou | The complexity of facets (and some facets of complexity[END_REF]. ♦ Remark 3 It is not known whether U-SAT is DP-complete: in [36, p. 415], it is said that "U-SAT is not believed to be DP-complete". In [START_REF] Blass | On the unique satisfiability problem[END_REF], it is shown that there exists one oracle under which U-SAT is not DP-complete; and one oracle under which it is, if NP =co-NP.

We are now ready to investigate the problems of the uniqueness of identifying and LD codes.

Some Easy Preliminary Results

These results are as old as the definitions of identifying and LD codes.

Lemma 4 (a) For any graph G = (V, E) of order n and any integer r ≥ 1,

we have LD r (G) ≥ ⌈log 2 (n -LD r (G) + 1)⌉. ( 2
)
(b) For any integer r ≥ 1 and any r-twin-free graph G = (V, E) of order n,

we have i r (G) ≥ ⌈log 2 (n + 1)⌉. (3)
Proof. (a) Let C be any r-LD code in G. All the n -|C| non-codewords v ∈ V \ C must be given nonempty and distinct sets B r (v) ∩ C constructed with the |C| codewords, so 2 |C| -1 ≥ n -|C|, from which (2) follows when C is optimal; (b) the argument is the same, but we have to consider all the n vertices v ∈ V , so 2 |C| -1 ≥ n. ♦ Lemma 5 Let r ≥ 2 be any integer and G = (V, E) be a graph. (a) A code C is 1-locating-dominating in G r , the r-th power of G, if and only if it is r-locating-dominating in G.

(b) A code C is 1-identifying in G r if and only if it is r-identifying in G.

Proof. (a) For every vertex v ∈ V , we have:

{c ∈ C : d G (v, c) ≤ r} = {c ∈ C : d G r (v, c) ≤ 1},
so if for all v ∈ V \ C, the sets on the left-hand side of the equality are nonempty and distinct, then the sets on the right-side also are, and viceversa; (b) same proof, for all v ∈ V . ♦

The following obvious lemma is often used implicitly; we give it without proof.

Lemma 6 Let r ≥ 1 be any integer and

G = (V, E) be a graph. (a) If C is r-locating-dominating in G, so is any set S ⊃ C. (b) If C is r-identifying in G, so is any set S ⊃ C. ♦ 3

Locating-Dominating Codes

After some necessary preliminary results, we are going to prove, for r ≥ 2 and q ≥ 1, the following polynomial reductions: U-SAT → p U-LDC 1 and U-SAT → p U-OLDC 1 (Theorem 14), U-SAT → p U-LDC r and U-SAT → p U-OLDC r (Theorem 15), U-LDC qr → p U-LDC q and U-OLDC qr → p U-OLDC q (Proposition 18), U-LDC 1 → p U-SAT (Theorem 19). The consequence of these reductions is that, for r ≥ 1, U-LDC r and U-OLDC r are NP-hard, and that U-SAT and U-LDC r have equivalent complexities; as a result, U-LDC r belongs to DP. We shall also show that U-OLDC r belongs to the class L N P (Proposition 22).

We do not have that U-OLDC r belongs to DP for lack of a polynomial reduction from U-OLDC 1 to U-SAT; we conjecture that such a reduction does not exist and that U-OLDC r / ∈ DP (see also Conclusion). Also note that the polynomial reduction U-SAT → p U-LDC 1 is a consequence of the chain of reductions U-SAT → p U-LDC r → p U-LDC 1 ; we still give Theorem 14 and its proof, because it constitutes a preliminary step for the proof of Theorem 15.

Preliminary Results

Lemma 7 Let h ≥ 1 and r ≥ 1 be integers; let G be a graph of order

2 h -1 + h with LD r (G) = h. Then:
(a) no vertex r-dominating 2 h-1 , or fewer, vertices can belong to an optimal r-locating-dominating code in G;

(b) no vertex r-dominating 2 h-1 + h + 1, or more, vertices can belong to an optimal r-locating-dominating code in G.

Proof. Let C be any optimal r-LD code in G: |C| = LD r (G) = h. Because there are 2 h -1 non-codewords, all the nonempty subsets of C coincide with all the nonempty, distinct sets B r (v) ∩ C, v ∈ V \ C. Then every codeword c appears exactly 2 h-1 times in these subsets, which means that c r-dominates exactly 2 h-1 non-codewords; since it r-dominates between one (itself) and h codewords, all in all it r-dominates between 2 h-1 + 1 and 2 h-1 + h vertices, and (a) and (b) follow. ♦

The following lemma is easy, and we prove only its last assertion.

Lemma 8 (a) The path P 5 = x 1 x 2 x 3 x 4 x 5 admits only one optimal 1-locating-

dominating code, C = {x 2 , x 4 }. (b) If we construct the graph G A = (V A , E A
) by adding to P 5 a vertex denoted by A together with the edge x 2 A, then A is 1-dominated by x 2 , but x 1 and A are not 1-separated by C.

(c) If G A is plunged in a larger graph G + with only A linked to the outside, then every optimal 1-locating-dominating code C + in G + contains x 2 and x 4 . At most one additional codeword, x 1 or A, may be necessary in

V A ∩ C + .
Proof. (c) Let C + be any optimal 1-LD code in G + . (i) If A is a codeword, obviously C + contains x 2 and x 4 , and no other codeword in P 5 . (ii) The same is true if A is not a codeword, but is 1-dominated by at least one outside codeword. (iii) Otherwise, C + contains x 2 , to 1-dominate A, it contains x 1 , otherwise x 1 and A are not 1-separated by C + , and it contains x 4 , which is the only vertex which 1-dominates x 5 and 1-separates A and x 3 at the same time.

♦

The statements of the following lemma have been given, although in a different way, in [13, proof of Lemma 3.1]; for completeness, we give here the (easy) proof.

Lemma 9 Let G i = (V i , E i ) be the following graph:

V i = {x i , x i , a i , b i , d i , f i , g i } and E i = {a i b i , b i x i , b i x i , x i d i , x i d i , d i f i , x i g i , x i g i },
and C i be a 1-locatingdominating code in G i , see Figure 2. Then: (a) at least one of x i and x i belong to C i ;

(b) at least two more codewords necessarily belong to C i , so that we have

LD 1 (G i ) ≥ 3; (c) we have LD 1 (G i ) = 3, and {x i , b i , d i } and {x i , b i , d i } are the only optimal 1-locating-dominating codes in G i ; (d) if G i is
plunged in a larger graph G + , with only x i and x i linked to the outside, then every 1-locating-dominating code in G + contains at least three codewords inside V i .

Proof. (a) Because x i and x i have the same neighbours in G i . (b) Because a i and f i must be 1-dominated by C i , we have

|C i ∩ {a i , b i }| ≥ 1 and |C i ∩ a i b i d i vertices outside x i vertices outside x i g i f i Figure 2:
The graph G i defined in Lemma 9. The black vertices form one of the two optimal 1-LD codes in

G i . q 1,1 p 1 q h,r-1 p 2 p p 3 h G s α clique x x V q 1,r-1
Figure 3: The graph G × has a unique optimal r-LD code, V × p .

{d i , f i }| ≥ 1. Alternatively, use (2) in Lemma 4. (c) Assume that it is x i that belongs to C i . Then taking a i and f i would not 1-dominate x i , and taking a i and d i , or b i and f i , would not 1-separate x i and f i , or x i and a i , respectively; on the other hand, {x i , b i , d i } is 1-LD. (d) Only x i and x i can be 1-dominated by the outside, and a i , f i and g i have to be 1-dominated by the code, so anyway at least three codewords are necessary inside V i . ♦

The previous two lemmas will be used in the proof of Theorem 14. In particular, Lemma 8(a) gives the example of a graph, P 5 , with a unique optimal 1-LD code. We want to have the same for any r > 1 (see Proposition 10(a)), in view of Theorem 15. We shall proceed as follows (see Figure 3):

We set h = 2r + 1, even if everything that follows also holds for any

h ≥ 2r + 1. Let G × p = (V × p , E × p ) be the cycle C h of length h, with V × p = {p i : 1 ≤ i ≤ h}. Then we construct G × q = (V × q , E × q ), with V × q = {q i,j : 1 ≤ i ≤ h, 1 ≤ j ≤ r -1} and E × q = ∪ 1≤i≤h {q i,j q i,j+1 : 1 ≤ j ≤ r -2}. The set of edges between G × p and G × q is E × p,q = {p i q i,1 : 1 ≤ i ≤ h}. Next, we construct G × s = (V × s , E × s ) with V × s = {s i : 1 ≤ i ≤ 2 h -1 -(r -1)h} and E × s = {s i 1 s i 2 : 1 ≤ i 1 < i 2 ≤ |V × s |}, i.e., G × s is a clique. We set V × = V × p ∪ V × q ∪ V × s .
In order to define the set E × q,s of edges between {q i,r-1 :

1 ≤ i ≤ h} and V × s , we introduce, for every vertex v ∈ V × q ∪ V × s , the signature of v as the set B r (v) ∩ V ×
p of the elements of the cycle that r-dominate v, and we wish to have nonempty and distinct signatures. Since

(a) the h vertices in V × p can provide 2 h -1 such signatures, (b) |V × q ∪ V × s | = |V × q | + |V × s | = 2 h -1, (c) the vertices in V ×
q have nonempty and different signatures (in particular, thanks to the fact that h ≥ 2r, all the vertices q i,1 have signatures of size 2r-1), (d) a vertex in V × s which is linked (respectively, not linked) to q i,r-1 is at distance equal to (respectively, greater than) r from p i , we can see that it is possible to construct E × q,s in such a way that the vertices in V × s have nonempty signatures which are different inside V × s , and different from those for V × q . In particular, in V × s there is a vertex which has signature equal to V × p ; we denote this vertex by α. Note also that we could not have more vertices with this signature property.

We set

E × = E × p ∪ E × p,q ∪ E × q ∪ E × q,s ∪ E × s and G × = (V × , E × ). The order of G × is n × = 2 h -1 + h.
We claim that, for a fixed r ≥ 2 and h = 2r + 1, C = V × p is the unique optimal r-LD code in G × ; we shall prove it by going through the following three easy facts.

Fact 1 For any r ≥ 2 and h = 2r + 1, the code C = V × p is an optimal r-locating-dominating code in G × .

Proof. When C = V × p , the signatures are the sets B r (v)∩C, for v ∈ V × \C. By construction, they are all nonempty and distinct, hence C is r-LD. The optimality comes from (2) in Lemma 4. ♦ Fact 2 For any r ≥ 2 and h = 2r + 1, the graph G × meets the conditions of Lemma 7.

Proof. Because LD r (G × ) = |V × p | = h and G × has order 2 h -1 + h. ♦ Fact 3 For any r ≥ 2 and h = 2r + 1, no vertex in V × q ∪ V × s can belong to any optimal r-locating-dominating code C in G × . Proof. Because V × s is a clique, every vertex q i,j , 1 ≤ i ≤ h, 1 ≤ j ≤ r -1, is within distance r from every vertex in V × s ; so every q i,j r-dominates at least |V × s | = 2 h -1 -(r -1)h vertices.
This number is greater than 2 h-1 + h + 1 for r ≥ 2 and h = 2r + 1. The same is true for the vertices in V × s . We can conclude using Lemma 7(b). ♦

We are now ready to prove the following proposition.

Proposition 10 Let r ≥ 2 and h = 2r + 1. Then: (a) the only optimal r-locating-dominating code in

G × is C = V × p ; (b) if G × is plunged in a larger graph G + = (V + , E + )
, with only α linked to the outside, then every optimal r-locating-dominating code in G + contains V × p .

Proof. (a) Now that Fact 3 has ruled out the vertices in V × q ∪ V × s , the only possibility left is to take all the h codewords in V × p . (b) Let C be an optimal r-LD code in G + , and let

|C ∩ (V × s \ {α})| = X and |C ∩ V × p | = Y . If Y = |V × p |, we are done, so we assume that Y ≤ h -1. How does C r-separate the 2 h -(r-1)h-2-X vertices in V ×
s \{α} that need to be r-separated? Depending on its distance to α, a vertex outside V × rdominates either α alone, or all the vertices in V × s plus all the vertices q i,j , 1 ≤ i ≤ h, for some j ≥ 1. This means that no outside codeword can r-separate the vertices in V × s \ {α}: this must be an inside-V × job. But the vertices in V × q ∪ V × s cannot do it either, because every such vertex rdominates all the vertices in V × s \ {α}; so the Y codewords in V × p must do it, and, according to whether the vertices in V × s \ {α} are r-dominated by other codewords or not, we must have 2

Y -ε ≥ 2 h -(r -1)h -2 -X, with ε = 0 or 1; since Y ≤ h -1, this implies 2 h-1 ≤ (r -1)h + 2 + X -ε. (4)
For r ≥ 2 and h = 2r + 1, the study of (4) shows that necessarily

X ≥ h + 2.
What is the role of these (at least) h + 2 codewords belonging to V × s \ {α}? (a) They contribute to r-dominate and r-separate some vertices in V + \ V × . From this perspective, all the vertices in V × s \ {α} have an equivalent role towards V + \ V × . So one codeword in V × s \ {α} is sufficient for this task.

(b) They contribute to r-dominate and r-separate some vertices in V × , and they themselves need not be r-separated from other vertices by the code; but we have already seen (Fact 1) that if we take the h vertices in V × p as codewords, then we can take care of all the vertices in V × .

(c) They contribute to r-separate some vertices in V + \ V × from some vertices in V × . But the h vertices in V × p r-dominate all the vertices inside V × and no vertex outside V × .

Therefore, if we take h codewords in V × p and one codeword in V × s \ {α}, we can do, with respect to the whole graph G + , at least as well as with X + Y ≥ X ≥ h + 2 codewords, contradicting the optimality of C. ♦

The following lemma and its obvious corollary will be used for Proposition 21. They characterize the vertices belonging to at least one optimal r-LD code, through the comparison of two 1-location-domination numbers.

Lemma 11 Let G = (V, E) be a graph. For a given vertex α ∈ V , we consider the following graph:

G α = (V α , E α ), with V α = V ∪ {β i : 1 ≤ i ≤ 6}, G α B α * α G=(V,E) β 3 4 6 β β β 1 2 β β 5
Figure 4: The graphs G and G α for Lemma 11.

E α = E ∪ {αβ i : i ∈ {1, 4}} ∪ {β i β i+1 : i ∈ {1, 2, 4, 5}},
where for i ∈ {1, . . . , 6}, β i / ∈ V (see Figure 4). Then α belongs to at least one optimal 1-locating-dominating code in G if and only if

LD 1 (G) = LD 1 (G α ) -2. Proof. Let B α = {β i : 1 ≤ i ≤ 6}, and B * α = {β i : i ∈ {2, 3, 5, 6}}
. First, we prove that α belongs to every optimal 1-LD code C α in G α : assume on the contrary that α / ∈ C α ; then obviously

|C α ∩ B α | ≥ 2 + 2, and (C α \ (C α ∩ B α )) ∪ {α, β 2 , β 5 } is a 1-LD code in G α , with fewer elements than C α , a contradiction. So α ∈ (C α ∩ V ).
(a) Assume that α belongs to at least one optimal 1-LD code C in G.

Then C α = C ∪ {β 2 , β 5 } is obviously 1-LD in G α , and LD 1 (G α ) ≤ |C α | = LD 1 (G) + 2.
Consider now an optimal 1-LD code C α in G α . Obviously, we have |C α ∩B * α | ≥ 1+1, and so, if we set C = C α ∩V , we have: |C| ≤ LD 1 (G α )-2. We have already established that α ∈ C α , and thus α ∈ C; now, we can see that it is sufficient, for any optimal 1-LD code in G α , to have two codewords in B α , namely β 2 and β 5 , and therefore

|C| ≥ LD 1 (G α ) -2. Now, no codeword in C α \ C 1-dominates any vertex in V , and necessarily C is a 1-LD code in G, which proves that LD 1 (G) ≤ |C| = LD 1 (G α ) -2.
So we can conclude that if α belongs to at least one optimal 1-LD code in G, then

LD 1 (G) = LD 1 (G α ) -2. (b) Assume now that LD 1 (G) = LD 1 (G α ) -2. Consider an optimal 1-LD code C α in G α , and let C = C α ∩ V . Then α ∈ C α and, exactly as before in (a), α ∈ C, C α = C ∪ {β 2 , β 5 }, C is a 1-LD code in G and its size is LD 1 (G α ) -2 = LD 1 (G), i.e.
, it is optimal (and contains α). ♦ Corollary 12 Let r ≥ 1 be any integer, G be a graph containing a vertex α, and G r be the r-th power of G. We construct the graph (G r ) α in the same way as in the previous lemma for G. Then α belongs to at least one optimal r-locating-dominating code in G if and only if

LD 1 (G r ) = LD 1 ((G r ) α ) -2.
Proof. Use Lemmas 5(a) and 11. ♦

In the following proposition, we shall only use the fact that LDC 1 belongs to NP, for Propositions 21 and 22. Proposition 13 [10, for r = 1], [START_REF] Charon | Minimizing the size of an identifying or locating-dominating code in a graph is NP-hard[END_REF] Let r ≥ 1 be any integer. The decision problem LDC r is NP-complete. ♦

The proofs of Proposition 13 do not treat however the problem of the uniqueness of a solution.

Uniqueness of Locating-Dominating Code

From U-SAT to U-LDC 1 and U-OLDC 1

Theorem 14 There exists a polynomial reduction from U-SAT to U-LDC 1 and to U-OLDC 1 : U-SAT → p U-LDC 1 and U-SAT → p U-OLDC 1 .

Proof. We give a polynomial reduction starting from an instance of U-SAT, that is, a collection C of m clauses over a set X of n variables.

For each variable x i ∈ X , 1 ≤ i ≤ n, we take the graph G i = (V i , E i ) defined in Lemma 9, identifying the literals x i , x i to the vertices x i , x i . For each clause c j , containing ε j literals, ε j ≥ 2, we create two vertices, A j and B j , and we link them to the ε j vertices corresponding, in the graphs G i , to the literals of c j . We also take a copy of P 5 , P 5 (A j ) = A j,1 A j,2 A j,3 A j,4 A j,5 , and link A j to A j,2 . We do the same for B j and a second copy of P 5 ,

P 5 (B j ) = B j,1 B j,2 B j,3 B j,4 B j,5 .
We call this graph G + , see Figure 5. The order of G + is 7n + 12m. Because the extremities of the copies of P 5 must be 1-dominated by a codeword, and thanks to Lemma 9(d), we have: LD 1 (G + ) ≥ 4m + 3n. We set k = 4m + 3n.

We claim that there is a unique solution to SAT if and only if there is a unique optimal 1-LD code in G + , and if and only if there is a unique 1-LD code of size at most k in G + .

(1) Assume first that there is a unique truth assignment satisfying all the clauses. We construct the following code C: for i ∈ {1, . . . , n}, among the vertices x i ∈ V i , x i ∈ V i , we put in C the vertex x i if the literal x i has been set TRUE, the vertex x i if the literal x i is FALSE, and we add b i and d i , as well as the second and fourth vertices in each of the copies of P 5 . Then C is a 1-LD code in G + : thanks to our preliminary observations (Lemmas 8 and 9), the only thing that remains to be checked is that for all j ∈ {1, . . . , m}, the code C 1-separates A j and A j,1 , B j and B j,1 , and this is so because there is at least one true literal in the clause c j , which means that A j and B j are 1-dominated by at least one codeword of type x i or x i .

Moreover, |C| = 3n + 4m = k, which proves that it is optimal, and no vertex A j nor B j is a codeword. This implies that, once we have decided between x i and x i , we have no choice left inside G i if we want a code of size k (optimal): we must take b i and d i , because neither x i nor x i is 1-dominated by any outside codeword; the same is true for the copies of P 5 , which must each contain their second and fourth vertices as only codewords.

Why is C unique? Suppose on the contrary that C * is another 1-LD code of size k = 3n + 4m in G + . Then |C * ∩ V i | = 3 for all i ∈ {1, . . . , n}, and at most one of x i and x i is in C * . Also, no vertex A j or B j is a codeword, and each copy of P 5 contains exactly two codewords, which are necessarily the second and the fourth ones. As another consequence, at least one of x i and x i is a codeword, because no codeword 1-separates them, and so exactly one of them belongs to C * . This defines a valid truth assignment for X , by setting

x i = T if x i ∈ C * , x i = F if x i ∈ C * . Since C = C * ,
this assignment is different from the assignment used to build C. But the fact that, for all j, C * 1-separates A j and A j,1 , B j and B j,1 , shows that there is a codeword x i or x i 1-dominating A j and B j , which means that the clause c j is satisfied. Therefore, we have a second assignment satisfying the instance of SAT, a contradiction. We can conclude that both problems, U-LDC 1 and U-OLDC 1 , also receive the answer YES.

(2) Assume next that the answer to U-SAT is NO: this may be either because no truth assignment satisfies the instance, or because at least two assignments do; in the latter case, this would lead, using the same argument as previously, to at least two (optimal) 1-LD codes (of size k), and a NO answer to both U-LDC 1 and U-OLDC 1 . So we are left with the case when the set of clauses C cannot be satisfied. This implies that no 1-LD code of size k exists, for the same reason as in the previous paragraph with C * ; this suffices to prove that we have also a NO answer to U-LDC 1 , but we have to go further for U-OLDC 1 . Assume then that C is an optimal 1-LD code of unknown size |C| > 4m + 3n. For 1

≤ j ≤ m, let A j = C ∩ {A j , A j,i : 1 ≤ i ≤ 5} and B j = C ∩ {B j , B j,i : 1 ≤ i ≤ 5}.
Suppose first that there is a j 0 such that A j 0 and B j 0 are not 1-dominated by any codeword x i nor any codeword x i . Then |A j 0 | > 2, and actually this set has size exactly three; the same is true for B j 0 . Now we have several optimal codes, because C ∩ (A j 0 ∪ B j 0 ) can be equal to {A j 0 , A j 0 ,2 , A j 0 ,4 , B j 0 , B j 0 ,2 , B j 0 ,4 }, or {A j 0 ,1 , A j 0 ,2 , A j 0 ,4 , B j 0 , B j 0 ,2 , B j 0 ,4 }, or {A j 0 , A j 0 ,2 , A j 0 ,4 , B j 0 ,1 , B j 0 ,2 , B j 0 ,4 }, -but in general, not {A j 0 ,1 , A j 0 ,2 , A j 0 ,4 , B j 0 ,1 , B j 0 ,2 , B j 0 ,4 }, for this might affect the vertices x i , x i to which A j 0 and B j 0 are linked.

So from now on, we assume that all vertices A j , B j are 1-dominated by at least one codeword x i or x i . Because the set of clauses cannot be satisfied, it is impossible that for all i, exactly one of x i and x i is a codeword, for this would lead to a valid truth assignment which would satisfy all the clauses. So there is a subscript i 0 such that either both x i 0 and x i 0 are codewords, or none is a codeword. If both are codewords, then C ∩ V i 0 contains x i 0 , x i 0 and can contain any combination with exactly one codeword among a i 0 , b i 0 and exactly one among d i 0 and f i 0 , yielding at least four optimal solutions. If none of x i 0 , x i 0 is a codeword, then they are 1-separated by some codeword(s) A j , B j ; moreover, g i 0 , which must belong to C, 1-dominates both x i 0 , x i 0 . Then again, we can have any of the four combinations with one codeword among a i 0 , b i 0 and one among d i 0 and f i 0 .

So in all cases, we do not have a unique optimal 1-LD code. ♦

Extension to r ≥ 2

It seems difficult to go directly from r = 1 to the general case r ≥ 2, and we start again from U-SAT, which does not change the final result; see [START_REF] Charon | Minimizing the size of an identifying or locating-dominating code in a graph is NP-hard[END_REF]Rem. 5] about this possible difficulty.

Theorem 15 Let r ≥ 2 be any integer. There exists a polynomial reduction from U-SAT to U-LDC r and to U-OLDC r : U-SAT → p U-LDC r and U-SAT → p U-OLDC r .

Proof. We give a polynomial reduction starting from an instance of U-SAT, i.e., a collection C of m clauses over a set X of n variables. We take the graph G + constructed in the proof of Theorem 14 (cf. Figure 5), and rename it G I = (V I , E I ), for Intermediate graph. Then, for each edge e = uv ∈ E I , we "paste" r -1 copies of the graph G × constructed for Proposition 10 (cf. Figure 3), by deleting the edge e = uv and creating the edges uα 1 , α 1 α 2 , . . ., α r-1 v, where the α i 's are copies of the vertex α in G × , see Figure 6: we shall say that the edge e is dilated. We denote by G + the graph thus constructed. Since r, hence h = 2r + 1, is fixed, the fact that G × has order 2 h + h -1 does not affect the polynomiality of our construction with respect to n + m. We set k = 3n + 4m + (r -1)h|E I |.

The use of copies of G × can be seen as a way of putting at distance r, in the graph G + , the vertices which are at distance one in G I , so that the vertices in V I will behave with respect to each other in a way very similar to the case r = 1. It is still true that, in addition to at least h codewords taken in each copy of G × , at least three codewords are necessary in order to deal with the vertices in each V i , and that at least two are necessary to cope with every copy of {x 1 , . . . , x 5 }, the set of vertices in P 5 . Consequently, any optimal r-LD code in G + has size at least k = 3n + 4m + (r -1)h|E I |, the three terms corresponding respectively to (a) the sets V i , 1 ≤ i ≤ n, (b) the 2m copies of P 5 (which are now dilated copies), and (c) the (r -1) copies of the graph G × on each edge of the intermediate graph G I .

One role of the codewords is to deal with the vertices in V I , that is, if these are not codewords themselves, to r-dominate them, and to r-separate between them -the domination and separation inside the copies of G × and the separation between vertices in V I and vertices in the copies of G × are already performed by the copies of the cycle C h , which are necessarily included in any optimal r-LD code in G + , as already observed.

We can also make the following useful remark.

Remark 16 Let C be any optimal r-locating-dominating code in + , e = uv be any edge in E I ,and G × be one of the copies pasted on e. If z is a codeword belonging to G × and not to its cycle C h , then (C \ {z}) ∪ {u} or (C \ {z}) ∪ {v} is also an optimal r-locating-dominating code in + . Indeed, if (a) z r-dominates neither u nor v, then it can be spared and C is not optimal; if (b) z r-dominates u, not v, i.e., it r-separates u and v (and z cannot r-dominate any other vertex in V I ), then, when u or v becomes a codeword, u and v need not be r-separated anymore; if (c) z r-dominates both u and v, these two vertices will remain r-dominated by a common codeword, u or v. In all cases, the fact that other vertices in V I can now be r-dominated by the substitute codeword (u or v) does not change anything (cf. Lemma 6(a)).

We claim that there is a unique solution to SAT if and only if there is a unique optimal r-LD code in G + , and if and only if there is a unique r-LD code of size at most k in G + .

(1) Assume first that there is a unique truth assignment satisfying all the clauses. We construct the following code C: for i ∈ {1, . . . , n}, among the vertices x i ∈ V i , x i ∈ V i , we put in C the vertex x i if the literal x i has been set TRUE, the vertex x i if the literal x i is FALSE, and we add b i and d i , as well as the second and fourth vertices in each of the (dilated) copies of P 5 . We add the cycle C h in each copy of G × . Then C is an r-LD code in G + : thanks to our preliminary observations, the only thing that remains to be checked is that for all j ∈ {1, . . . , m}, the code C r-separates A j and A j,1 , B j and B j,1 , and this is so because there is at least one true literal in the clause c j , which means that A j and B j are r-dominated by at least one codeword of type x i or x i : everything develops exactly as in the case r = 1.

Moreover, |C| = k, which proves that it is optimal, and no vertex A j nor B j is a codeword. This implies that, once we have decided between x i and x i , we have no choice left inside G i : we must take b i and d i , because neither x i nor x i is r-dominated by any outside codeword. We have no choice in the copies of P 5 either: no pair of vertices in copies of G × can r-dominate the first and last vertices, and r-separate the first, third and last, at the same time: only the second and fourth vertices can perform this.

Why is C unique? Suppose on the contrary that C * is another (optimal) r-LD code (of size k) in G + . Then each copy of G × intersects C * on exactly h vertices which are the vertices of the cycle C h ; also, |C * ∩ V i | = 3 for all i ∈ {1, . . . , n}, and at most one of x i and x i is in C * . Moreover, no vertex A j nor B j is a codeword. As a consequence, at least one of x i and x i is a codeword, because no codeword r-separates them, and so exactly one of them belongs to C * . This defines a valid truth assignment for X , by setting

x i = T if x i ∈ C * , x i = F if x i ∈ C * . Since C = C * ,
this assignment is different from the assignment used to build C. But the fact that, for all j, C * r-separates A j and A j,1 , B j and B j,1 , shows that there is a codeword x i or x i r-dominating A j and B j , which means that the clause is satisfied. Therefore, we have a second assignment satisfying the instance of SAT, a contradiction.

(2) Assume next that the answer to U-SAT is NO: this may be either because no truth assignment satisfies the instance, or because at least two assignments do; in the latter case, this would lead, using the same argument as previously, to at least two optimal r-LD codes (of size k), and a NO answer to U-LDC r and U-OLDC r . So we are left with the case when the set of clauses C cannot be satisfied. This implies that no r-LD code of size k exists; this ends the case of U-LDC r but we have to go on with U-OLDC r : assume that C is an optimal r-LD code of unknown size |C| > k, with at least three codewords to deal with each V i , at least two codewords to deal with each copy of P 5 , at least h codewords in each copy of G × , and possibly vertices of type A j , B j . By Remark 16, if there is a codeword belonging to a copy of G × and not to its cycle C h , then we have at least two optimal r-LD codes, and we are done. So from now on we assume that no copy of G × contains codewords outside the cycle C h . Then C contains at least three codewords in each V i , at least two codewords in each copy of P 5 , exactly h codewords in each copy of G × , and possibly vertices of type A j and B j . Now the argument of the case r = 1 (Theorem 15) can be repeated almost word for word: first, we can exclude that there is a vertex A j 0 not r-dominated by any codeword x i or x i ; then we deal with the cases when both x i and x i are codewords, and when none of them is. In all cases, we have more than one optimal r-LD code in G + . ♦ Corollary 17 Let r ≥ 1 be any integer. The decision problems U-LDC r and U-OLDC r are NP-hard.

Proof. Because U-SAT is NP-hard (Proposition 2). ♦ Proposition 18 Let r ≥ 2 and q ≥ 1 be any integers. There is a polynomial reduction from U-LDC qr to U-LDC q and from U-OLDC qr to U-OLDC q : U-LDC qr → p U-LDC q and U-OLDC qr → p U-OLDC q . As a particular case, we have U-LDC r → p U-LDC 1 and U-OLDC r → p U-OLDC 1 .

Proof. Let (G, k) be an instance of U-LDC qr and G be an instance of U-OLDC qr , for r ≥ 2 and q ≥ 1. The instance for U-LDC q is simply (G r , k), and G r for U-OLDC q , where G r is the r-th power of G: obviously, by Lemma 5(a), there is a unique q-LD code of size k in G r if and only if there is a unique qr-LD code of size k in G, and there is a unique optimal q-LD code in G r if and only if there is a unique optimal qr-LD code in G. ♦

An Upper Bound for the Complexity of U-LDC r

Theorem 19 exists a polynomial reduction from U-LDC 1 to U-SAT: U-LDC 1 → p U-SAT.

Proof. In [START_REF] Hudry | Complexity of unique (optimal) solutions in graphs: Vertex Cover and Domination[END_REF]Rem. 10] we developed a general argument for this kind of reduction, with three types of clauses, one type for the description of the specific problem, here the fact that we want the code to be 1-LD, one type for the fact that we want a code of size at most k, and one type to break the multiple solutions. The same method will be applied for Theorem 34, with 1-identifying codes. We start from an instance of U-LDC 1 : a graph G = (V, E) and an integer k, with V = {x 1 , . . . , x |V | }; we assume that |V | ≥ 3. We create the set of k|V | variables X = {x i m : 1 ≤ i ≤ |V |, 1 ≤ m ≤ k} and the following clauses:

(a1) for each vertex x i ∈ V with neighbours x n 1 , . . . , x ns (where s = s(x i ) is the degree of x i ), we take the clause of size k(s + 1):

c x i = {x i 1 , x i 2 , . . . , x i k , x n 1 1 , x n 1 2 , . . . , x n 1 k , x n 2 1 , . . . , x n 2 k , .
. . , x ns 1 , . . . , x ns k }; (a2) for each pair of vertices x i ∈ V , x j ∈ V , we consider the set B 1 (x i )∆ B 1 (x j ) = {x h 1 , x h 2 , . . . , x h ℓ } (where ℓ depends on x i and x j ) and we construct the clause c x i x j :

{x i 1 , x i 2 , . . . , x i k , x j 1 , . . . , x j k , x h 1 1 , x h 1 2 , . . . , x h 1 k , x h 2 1 , . . . , x h 2 k , . . . , x h ℓ 1 , . . . , x h ℓ k };
we shall say that {x i 1 , x i 2 , . . . , x i k , x j 1 , . . . , x j k } is the first part of c x i x j and {x h 1 1 , x h 1 2 , . . . , x h 1 k , x h 2 1 , . . . , x h 2 k , . . . , x h ℓ 1 , . . . , x h ℓ k } its second part, which exists only when ℓ > 0 and may contain variables also appearing in the first part, which is unimportant;

(b1) for 1 ≤ m ≤ k and 1 ≤ h < ℓ ≤ |V |, we construct clauses of size two:

{x h m , x ℓ m }; (b2) for 1 ≤ m < s ≤ k and 1 ≤ h ≤ |V |, we construct clauses of size two: {x h m , x h s }; (c) 1 ≤ m < k and 1 < ℓ ≤ |V |, for 1 ≤ h < ℓ
and m < s ≤ k, we construct clauses of size two: {x ℓ m , x h s }. All these clauses constitute the instance of U-SAT. Note that the number of variables and clauses is polynomial with respect to the order of G, since we may assume that k ≤ |V |.

Assume that we have a unique 1-LD code of size k in G, C = {x p 1 , x p 2 , . . . , x p k }, with p 1 < p 2 < . . . < p k . We can see that C is optimal (otherwise, any optimal 1-LD code contradicts our uniqueness assumption). Define the assignment A 1 by A 1 (x pq q ) = T for 1 ≤ q ≤ k, and all the other variables are set FALSE by A 1 . We claim that this assignment satisfies all the clauses; indeed:

(a1) at least one among x i and its neighbours is a codeword, so the clause c x i is satisfied by A 1 .

(a2) (i) If at least one of x i or x j belongs to C, say x i = x pq ∈ C, then the variable x pq q = x i q has been set True by A 1 and the first part of the clause c x i x j , hence the whole clause, is satisfied. (ii) If neither x i nor x j belongs to C, then, using the characterization given by (1), we can see that at least one x hm belongs to C, which guarantees that the second part of c x i x j is satisfied.

(b1) If a clause {x h m , x ℓ m } is not satisfied for some m, h, ℓ, this means that A 1 (x h m ) = A 1 (x ℓ m ) = T, i.e., two different vertices are the m-th element in C.

(b2) If {x h m , x h s } is not satisfied, then x h appears at least twice in C. (c) If {x ℓ m , x h s } is not satisfied for some m, ℓ, with h < ℓ and m < s, then

A 1 (x ℓ m ) = A 1 (x h s ) = T.
This means that x ℓ = x pm and x h = x ps ; so ℓ = p m , h = p s . Now h < ℓ implies that p s < p m , but m < s implies that p m < p s , a contradiction.

Is A 1 unique? Assume on the contrary that another assignment, A 2 , also satisfies the constructed instance of U-SAT. We construct a new code C + by putting in C + the vertex x h as soon as some variable x h m is set TRUE by A 2 . Now the satisfaction, by A 2 , of the clause c x i in (a1) proves that every vertex in V is 1-dominated by C + ; the satisfaction of c x i x j from (a2) means that at least one vertex among x i , x j , x h 1 , . . . , x h ℓ belongs to C + . So for every pair of vertices x i , x j , either one of them is in the code, or an element in B 1 (x i )∆B 1 (x j ) is in the code. So every pair of non-codewords is 1-separated by C + .

Therefore, we have just proved that C + is a 1-LD-code. Using (b1) for A 2 , we can see that for each m ∈ {1, . . . , k} there is at most one variable with subscript m that is set TRUE by A 2 ; this means that we have constructed a 1-LD code with (at most) k elements. Since such a code is unique by assumption, we can see that A 1 and A 2 "selected" the same k codewords: for each p q ∈ {p 1 , . . . , p k }, we already know that there is exactly one variable, x pq q , set TRUE by A 1 , and, using (b2) after (b1) for A 2 , exactly one variable, say x pq t , set TRUE by A 2 . It is now time to use (c) in order to prove that q = t for every p q , so that A 1 and A 2 actually coincide: indeed, assume on the contrary that for some q ∈ {1, . . . , k}, we have q = t; we treat the case 1 ≤ q < t ≤ k, the case 1 ≤ t < q ≤ k being analogous. If we consider the subscripts smaller than t, there must be one, say v, such that there is a superscript p u > p q verifying A 2 (x pu v ) = T. Now the clause {x pu v , x pq t } from (c) is not satisfied by A 2 , a contradiction. So a YES answer to U-LDC 1 leads to a YES answer to U-SAT. Assume now that the answer to U-LDC 1 is negative. If it is negative because there are at least two 1-LD codes of size k, 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 1-LD code, and different 1-LD codes obviously lead to different assignments. On the other hand, if there is no 1-LD code of size k, then there can be no assignment satisfying U-SAT, because such an assignment would give a 1-LD code of size k, as we have seen above when dealing with A 2 . So in both cases, a NO answer to U-LDC 1 implies a NO answer to U-SAT. ♦ By Proposition 18 or its corollary, this immediately implies that there is a polynomial reduction from U-LDC r to U-SAT.

Theorem 20 Let r ≥ 1 be any integer. The problem U-LDC r has complexity equivalent to that of U-SAT. As a consequence, U-LDC r belongs to the class DP. ♦ Note that it could have been shown directly that U-LDC r belongs to DP.

Two Upper Bounds for the Complexity of U-OLDC r

In [START_REF] Hudry | Complexity of unique (optimal) solutions in graphs: Vertex Cover and Domination[END_REF], we give, for two problems structurally similar to U-OLDC r , two upper bounds, the first one being weaker but constructive. We do not give the proofs of the following two results but refer to [START_REF] Hudry | Complexity of unique (optimal) solutions in graphs: Vertex Cover and Domination[END_REF] instead. These proofs use Lemma 11, Corollary 12 and Proposition 13.

Proposition 21 For r ≥ 1, the decision problem U-OLDC r belongs to the class P N P . In case of a YES answer, one can give the only optimal rlocating-dominating code within the same complexity. ♦ Proposition 22 For r ≥ 1, the decision problem U-OLDC r belongs to L N P . ♦

Identifying Codes

The structure of this Section and its results are the same as Section 3 for LD-codes, although the preliminary graphs and arguments are quite different technically.

Preliminary Results

Lemma 23 will be used in the proof of Theorem 30, and Lemma 24 in the proofs of Theorems 30 and 31.

Lemma 23 Let G × = (V × , E × ) be the following graph:

V × = {α, β 1 , β 2 , β 3 , β 4 , β 5 , β 6 , ω, δ, σ, τ, λ, µ},
E × = {αβ 1 , β 1 β 2 , β 1 δ, β 1 ω, β 2 δ, β 2 ω, β 1 β 3 , β 3 β 4 , β 3 σ, β 3 τ, β 4 σ, β 4 τ } ∪ ∪ {αβ 5 , β 5 β 6 , β 5 λ, β 5 µ, β 6 λ, β 6 µ}, see Figure 7(a). Then i 1 (G × ) = 8, any 1-identifying code in G × contains the set of vertices C = {α, β 1 , ω, δ, σ, τ, λ, µ}, and C is the only optimal 1-identifying code in G × .
If G × is plunged in a larger graph G + , with only α linked to the outside, then every 1-identifying code in G + contains C; the outside neighbours of α are 1-covered, not 1-separated, by α, and they are 1-separated from V × by C.

Proof. Straightforward: α is the only vertex 1-separating β 5 and β 6 ; the same is true about β 1 , for β 3 , β 4 ; about ω, for β 2 , δ; about δ, for β 2 , ω; about σ, for β 4 , τ ; about τ , for β 4 , σ; about λ, for β 6 , µ; and about µ, for β 6 , λ. So these eight vertices belong to any 1-identifying code, and since they obvioulsy constitute a 1-identifying code, this is the only optimal 1-identifying code.

When we consider G + , all the above arguments still work. ♦

The statements of the following lemma have been given, although in a different way, in [14, proof of Th. 5.1]; for completeness, we give here the (easy) proof.

Lemma 24 Let G i = (V i , E i ) be the following graph:

V i = {x i , x i , a i , b i , d i , f i } and E i = {a i b i , b i x i , b i x i , x i d i , x i d i , d i f i }, and C i be a 1-identifying code in G i , see Figure 7(b). Then (a) At least one of x i and x i belong to C i . (b) At least two more codewords are necessary in C i , so that i 1 (G i ) ≥ 3. (c) We have i 1 (G i ) = 3, and {x i , b i , d i } and {x i , b i , d i } are the only optimal 1-identifying codes in G i . (d) If G i is
plunged in a larger graph G + , with only x i and x i linked the outside, then every 1-identifying code in G + contains at least three codewords in V i , and one of them is x i or x i .

Proof. (a) Because a i and b i , or d i and f i , must be 1-separated by C i . (b) Because a i and f i must be 1-covered by C i . Alternatively, use (3) in Lemma 4. (c) Assume that it is x i that belongs to C i . Then taking a i and f i would not 1-cover x i , and taking a i and d i , or b i and f i , would not 1-separate x i and d i , or x i and b i , respectively; on the other hand, {x i , b i , d i } is 1-identifying. (d) Only x i and x i can be 1-covered by the outside, and a i and f i still have to be 1-covered, a i and b i , and d i and f i still must be pairwise 1-separated by a codeword, requiring at least three inside codewords, one of them being x i or x i . ♦

The diapason and shortened diapason, introduced in the following lemma and its corollary, will be used in the proof of Theorem 31.

Lemma 25 [13,

{t i t i+1 : i = 1, 2, . . . , r -1} ∪ {t r y 1 , t r z 1 } ∪ {y i y i+1 , z i z i+1 : i = 1, 2, . . . , 2r}.
(a) The smallest r-identifying code in ∆, C 0 , has size 2r + 2 and is unique: it consists of the vertices y 1 , y 2 , . . . , y r , y 2r+1 , z 1 , z 2 , . . . , z r , and z 2r+1 .

(b) Any r-identifying code in ∆ contains at least 2r+2 elements in Y ∪Z; among them, the 2r vertices y 1 , y 2 , . . . , y r and z 1 , z 2 , . . . , z r must belong to any r-identifying code.

(c) Consider r -1 copies, ∆ 1 , ∆ 2 , . . . , ∆ r-1 , of the graph ∆, and in each copy rename the "first" vertex t 1 by t 1,1 , t 2,1 , . . . , t r-1,1 , and the other vertices accordingly. Build the graph Ω (cf. Figure 9) by taking these r -1 copies and adding the edges t 1,1 t 2,1 , t 2,1 t 3,1 , . . . , t r-2,1 t r-1,1 . Then the smallest r-identifying code in Ω, C 1 , has size (r -1)(2r + 2), is unique and consists of r -1 copies of the code C 0 , one copy of C 0 in each copy of ∆.

copies of t r-1,1 t 2,1 t 1,r t 1,1 ∆ 1 ∆ 2 r-1 ∆ ∆ z r-1,2r+1
(d) If Ω is plunged in a larger graph G + , with only t 1,1 and t r-1,1 linked to the outside, then every r-identifying code in G + contains C 1 ; no outside vertex is r-covered by C 1 . ♦

We call the graph ∆ a diapason. The sets Y and Z are the branches, the set T the stem, the vertex t 1 the foot of the diapason.

Corollary 26 If we modify the previous lemma by considering a set T - with one vertex less: T -= {t 1 , t 2 , . . . , t r-1 } and t r-1 linked to y 1 and z 1 , and if we denote by ∆ -the graph thus obtained, then the statements (a) and (b) of Lemma 25 remain true when we replace ∆ by ∆ -. If ∆ -is plunged in a larger graph G + , with only t 1 linked to the outside, then every r-identifying code in G + contains C 0 ; the outside neighbours of t 1 are the only outside vertices r-covered by C 0 , they are not r-separated from one another by C 0 , and they are r-separated by C 0 from all the vertices in ∆ -. ♦

We call the graph ∆ -a shortened diapason.

Lemma 27 below, and its corollary, are similar to Lemma 11 and Corollary 12 on r-LD codes: they characterize the vertices belonging to at least one optimal r-identifying code, through the comparison of two 1-identification numbers. They will be used for Proposition 36. They are simplified versions of [START_REF] Hudry | More results on the complexity of identifying problems in graphs[END_REF]Lemma 3] and [START_REF] Hudry | More results on the complexity of identifying problems in graphs[END_REF]Cor. 4], respectively.

Lemma 27 Let G = (V, E) be a 1-twin-free graph. For a given vertex α ∈ V , we construct the following graph G α = (V α , E α ):

V α = V ∪ {β 1 , β 2 , δ, λ}, E α = E ∪ {αβ 1 , β 1 β 2 , β 1 δ, β 1 λ, β 2 δ, β 2 λ},
where none of the vertices β 1 , β 2 , δ, λ belongs to V . Then α belongs to at least one optimal 1-identifying code in G if and only if i

1 (G) = i 1 (G α ) -2. ♦
Corollary 28 Let r ≥ 1 be any integer, G be an r-twin-free graph containing a vertex α, and G r be the r-th power of G. We construct the graph (G r ) α in the same way as in the previous lemma for G. Then α belongs to at least one optimal r-identifying code in G if and

only if i 1 (G r ) = i 1 ((G r ) α ) -2. ♦
In the following proposition, we shall only use the fact that IdC 1 belongs to NP (see Propositions 36 and 37).

Proposition 29 [14, for r = 1], [START_REF] Charon | Minimizing the size of an identifying or locating-dominating code in a graph is NP-hard[END_REF] Let r ≥ 1 be any integer. The decision problem IdC r is NP-complete. ♦

But the proofs for Proposition 29 do not deal with the problem of the uniqueness of a solution. Proof. This proof is inspired by that of the NP-completeness of IdC 1 in [START_REF] Cohen | On identifying codes[END_REF]. We give a polynomial reduction starting from an instance of U-SAT, that is, a collection C of m clauses over a set X of n variables.

Uniqueness of Identifying Code

For each variable x i ∈ X , 1 ≤ i ≤ n, we take the graph G i = (V i , E i ) defined in Lemma 24. For each clause c j , containing ε j literals, ε j ≥ 2, we create two vertices, A j and B j , and we link A j to the ε j vertices corresponding, in the graphs G i , to the literals of c j . Finally we link the vertices A j and B j to one copy of the graph G × defined in Lemma 23, one different copy for each couple (A j , B j ), by creating the edges A j α and B j α (or rather: we use the j-th copy of α); we call this graph G + , see Figure 10. The order of G + is 6n + 15m. Note that each pair of vertices A j , B j , 1 ≤ j ≤ m, is 1-covered by a copy of α (which belongs necessarily to any 1-identifying code in G + , see Lemma 23). By Lemmas 23 and 24, we have i 1 (G + ) ≥ 8m + 3n. We set k = 8m + 3n.

We claim that there is a unique solution to SAT if and only if there is a unique optimal 1-identifiying code in G + , and if and only if there is a unique 1-identifying code of size at most k in G + .

(1) Assume first that there is a unique truth assignment satisfying all the clauses. We construct the following code C: for i ∈ {1, . . . , n}, among the vertices x i ∈ V i , x i ∈ V i , we put in C the vertex x i if the literal x i has been set TRUE, the vertex x i if the literal x i is FALSE, and we add b i and d i . We add all the copies of the vertices α, β 1 , ω, δ, σ, τ , λ and µ. Then C is a 1-identifying code in G + : thanks to all our preliminary observations (Lemmas 23 and 24), the only thing that remains to be checked is that for all j ∈ {1, . . . , m}, the vertices A j and B j are 1-separated by C. And this is so because there is at least one true literal in the clause c j . Moreover, |C| = k, which proves that it is optimal. We can also see that, once we have decided between x i and x i , we have no choice left inside G i : we must take b i and d i , because neither x i nor x i is 1-covered by outside codewords, due to the fact that no vertex A j can be a codeword, by an argument of cardinality.

Why is C unique? Suppose on the contrary that C * is another 1identifying code of size k in G + . Then |C * ∩ V i | = 3 for all i ∈ {1, . . . , n}, and exactly one of x i and x i is in C * . This defines a valid truth assignment for X , by setting

x i = T if x i ∈ C * , x i = F if x i ∈ C * . Since C = C * ,
this assignment is different from the assignment used to build C. But the fact that C * 1-separates A j and B j for all j shows that there is a codeword x i or x i 1-covering A j , which means that the clause is satisfied. Therefore, we have a second assignment satisfying the instance of SAT, a contradiction.

(2) Assume next that the answer to U-SAT is NO: this may be either because no truth assignment satisfies the instance, or because at least two assignments do; in the latter case, this would lead, using the same argument as previously, to at least two optimal 1-identifying codes (of size k), and a NO answer to U-IdC 1 and U-OIdC 1 . So we are left with the case when the set of clauses C cannot be satisfied. This implies that no 1-identifying code of size k exists; the case U-IdC 1 is closed, and, to go on with the problem U-OIdC 1 , we assume that C is an optimal 1-identifying code of unknown size |C| > 8m + 3n. We know that each copy of G × contains at least eight codewords, and each G i at least three codewords. Where can the extra codeword(s) be? Any additional codeword in a copy of G × is useless with respect to 1-identification and can be saved. If there are five or six codewords in a G i , at least one can be saved; assume next that there are four of them: (a) if both x i and x i are codewords, then, e.g.,

C ∩ V i = {x i , x i , b i , d i } or C ∩ V i = {x i , x i , b i , f i }
can be part of an optimal solution; (b) if only one of x i and x i , say x i , is a codeword, then there are also several possibilities for C ∩ V i , such as {x i , b i , d i , a i } and {x i , b i , d i , f i }. So we can conclude that there are eight codewords in each copy of G × , three codewords in each G i and the extra codewords are among the vertices A j , B j . If for some j, B j ∈ C and A j / ∈ C, then B j serves as a codeword only to 1-separate itself from A j , but this can be done by A j , so (C \{B j })∪{A j } would be another optimal 1-identifying code. So we are left with the case A j ∈ C. Then A j 1-covers one vertex x i or x i , say x i , and then both

C ∩ V i = {x i , b i , d i } and C ∩ V i = {x i , a i , f i } are possible.
In all cases, we have proved that there are several optimal 1-identifying codes in G + , i.e., we have a NO answer to the constructed instance of U-OIdC 1 . ♦

Extension to r ≥ 2

As for LD codes, we do not go directly from r = 1 to r ≥ 2, but start again from U-SAT, which does not change the final result; see [13, Rem. 2] about this difficulty.

Theorem 31 Let r ≥ 2 be any integer. There exists a polynomial reduction from U-SAT to U-IdC r and to U-OIdC r : U-SAT → p U-IdC r and U-SAT → p U-OIdC r .

Proof. This proof is inspired by that of the NP-completeness of IdC r in [START_REF] Charon | Minimizing the size of an identifying or locating-dominating code in a graph is NP-hard[END_REF].

We give a polynomial reduction starting from an instance of U-SAT, i.e., a collection C of m clauses over a set X of n variables.

In a first step, for each variable x i ∈ X , 1 ≤ i ≤ n, we take the graph G i = (V i , E i ) defined in Lemma 24. For each clause c j , containing ε j literals, ε j ≥ 2, we create two vertices, A j and B j , and the edge A j B j , and we link A j to the ε j vertices corresponding, in the graphs G i , to the literals of c j ; we call these edges "membership edges". So far, we have constructed an intermediate graph, G I = (V I , E I ).

In a second step (see Figure 11), for each membership edge and for each edge in the graphs G i , we "paste" one copy of the graph Ω defined in The diapasons can be seen as a way of putting at distance r, in the graph G + , the vertices in V i , 1 ≤ i ≤ n, and {A j : 1 ≤ j ≤ m} which are at distance one from one another in G I . And so these vertices will behave with respect to each other in a way very similar to the case r = 1. In particular, it is still true that, in addition to codewords taken in the branches of the diapasons, at least three codewords are necessary to deal with the vertices in each V i . Consequently, by Lemma 25(b), any optimal r-identifying code in G + has size at least 3n + (r -1)(2r + 2)(|E I |m) + m(2r + 2) = k, the three terms corresponding respectively to (a) the sets V i , 1 ≤ i ≤ n, (b) the r -1 copies of the diapason on each edge which is not A j B j , and (c) the copy of the shortened diapason on each edge A j B j , 1 ≤ j ≤ m.

The role of the copies of the shortened diapason is to r-cover A j and B j without r-separating them, and to r-separate A j and B j from the other vertices belonging to V I .

After these introductory observations, we can conclude that, in any ridentifying code in G + , the role of the codewords which do not belong to the branches of the diapasons, is (a) to r-separate A j from B j , for all j ∈ {1, . . . , m}; (b) to r-cover all the vertices in V i , and to r-separate them, for all i ∈ {1, . . . , n}.

We claim that there is a unique solution to SAT if and only if there is a unique optimal r-identifiying code in G + , and if and only if there is a unique r-identifying code of size at most k in G + .

(1) Assume first that there is a unique truth assignment satisfying all the clauses. We construct the following code C: for i ∈ {1, . . . , n}, among the vertices x i ∈ V i , x i ∈ V i , we put in C the vertex x i if the literal x i has been set TRUE, the vertex x i if the literal x i is FALSE, we add b i and d i , and we also take the unique optimal r-identifying codes in all the copies of Ω and ∆ -. Then, as in the case r = 1, we can check that C is an r-identifying code in G + ; in particular, for all j ∈ {1, . . . , m}, the vertices A j and B j are r-separated by C, because there is at least one true literal in the clause c j . Also, the code C has the right size and is optimal. We can also see that, once we know that, say, x i ∈ C, we have no choice left for the completion of the code, because a i , f i and x i must be r-covered (the latter because no A j is a codeword), and x i , b i and d i must be r-separated by the code. So b i and d i necessarily are the remaining two codewords in V i , for all i ∈ {1, . . . , n}.

Why is C unique? Suppose on the contrary that C * is another ridentifying code, with |C * | = |C|. Then for all i ∈ {1, . . . , n}, exactly three codewords take care of V i , and C * contains b i , d i and exactly one of x i and x i . This defines a valid truth assignment for X , by setting x i = T if x i ∈ C * , x i = F if x i ∈ C * . Since C = C * , this assignment is different from the assignment used to build C. But the fact that C * r-separates A j and B j for all j shows that there is one codeword x i or x i r-covering A j , which means that the clause is satisfied. Therefore, we have a second assignment satisfying the instance of SAT, a contradiction.

(2) Assume next that the answer to U-SAT is NO: this may be either because no truth assignment satisfies the instance, or because at least two assignments do; in the latter case, this would lead, using the same argument as previously, to at least two optimal r-identifying codes (of size k), and a NO answer to U-IdC r and U-OIdC r . So we are left with the case when the set of clauses C cannot be satisfied. This implies that no r-identifying code of size k exists: we have ended the case U-IdC r ; next, we assume that C is an optimal r-identifying code of unknown size |C| > k. We know that each copy of Ω or of ∆ -contains at least (r -1)(2r + 2) or 2r + 2 codewords, respectively, and that each V i requires at least three codewords. Now, where can the extra codeword(s) be?

Note that, unfortunately, Remark 16 cannot be adapted to the present construction with pasted diapasons for r-identifying codes, because in the case (b) of the Remark, when the codeword z belonging to a diapason rseparates u and v and is replaced by u or v, then u and v are not r-separated anymore. This did not matter with LD-codes, but it does for identifying codes.

Any vertex B j is a useless codeword, because, even in the case r = 2, it r-covers both A j and itself. This is also true for all the codewords that would be on the branches of any diapason (apart from the codewords y 1 , y 2 , . . . y r , y 2r+1 and z 1 , z 2 , . . . , z r , z 2r+1 ), as well as for codewords on the stem of a shortened diapason (for they all r-cover both A j and B j ). Proposition 36 For r ≥ 1, the decision problem U-OIdC r belongs to the class P N P . In case of a YES answer, one can give the only optimal ridentifying code within the same complexity. ♦ Proposition 37 For r ≥ 1, the decision problem U-OIdC r belongs to L N P . ♦

Conclusion

We have established that the four decision problems U-LDC r , U-IdC r , U-OLDC r and U-OIdC r are, for any fixed r ≥ 1, NP-hard, and that the two problems U-OLDC r and U-OIdC r belong to the class L N P . For U-LDC r and U-IdC r , we could go further and prove that they are equivalent to U-SAT and therefore belong to the class DP.

Conjecture Neither U-OLDC r nor U-OIdC r belong to DP.

Open Problem Give a better location, in the classes of complexity, for the problems U-LDC r , U-IdC r , U-OLDC r and U-OIdC r .

We can see in Figure 12 that U-SAT, U-LDC r and U-IdC r are in the vertically hatched region, but probably not in DP-complete, whereas U-OLDC r and U-OIdC r are somewhere in the region that is hatched horizontally or vertically.

In [START_REF] Blidia | Characterizations of trees with unique minimum locating-dominating sets[END_REF], a characterization of the trees which admit a unique optimal 1-LD code is given.

Open Problems Extend this study to other classes of graphs; to any integer r ≥ 1; to identifying codes. What is the complexity of the sub-problem of U-OLDC 1 when the instance is any tree.

In [START_REF] Blass | On the unique satisfiability problem[END_REF], 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.

Figure 1 :

 1 Figure 1: Some classes of complexity.

Figure 5 :

 5 Figure 5: For r = 1, the graph G + , constructed from a set of clauses.

Figure 6 :

 6 Figure 6: How the edge e = uv ∈ E I is dilated in the proof of Theorem 15.

Figure 7 :

 7 Figure 7: (a) The graph G × of Lemma 23. Black vertices belong to any 1-identifying code in G × . (b) The graph G i of Lemma 24, with an optimal 1-identifying code (black vertices).

Figure 8 :

 8 Figure 8: The diapason-graph ∆.

Figure 9 :

 9 Figure 9: The graph Ω.

4. 2 . 1 1 Theorem 30

 21130 From U-SAT to U-IdC 1 and U-OIdC There exists a polynomial reduction from U-SAT to U-IdC 1 and to U-OIdC 1 : U-SAT → p U-IdC 1 and U-SAT → p U-OIdC 1 .

Figure 10 :

 10 Figure 10: For r = 1, the graph G + , constructed from a set of clauses.

Figure 11 :

 11 Figure 11: How the edge e ∈ E I is transformed in the proof of Theorem 31.If e is a membership edge or an edge in G i , we use a copy of Ω; if e = A j B j , we use a copy of ∆ -.

Figure 12 :

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

4. 2 . 4

 24 Two Upper Bounds for the Complexity of U-OIdC r Exactly as in Section 3.2.4, we give, without proof, two results on U-OIdC r ; this time, Lemma 27, Corollary 28 and Proposition 29 are used.

  Lemma 2.1, Cor. 2.1] Let r ≥ 2 be any integer. Let T = {t 1 , t 2 , . . . , t r }, Y = {y 1 , y 2 , . . . , y 2r+1 }, and Z = {z 1 , z 2 , . . . , z 2r+1 }. Let ∆ be the graph in Figure8, with vertex set T ∪ Y ∪ Z and edge set

Let us now consider the case of a codeword on the stem of a diapason pasted on an edge e = uv: this edge is either a membership edge or an edge in some G i ; the (only) role of this codeword is either to r-cover exactly one of u an v, and consequently to r-separate u from v, or to r-cover both u and v, and consequently to r-separate them from other vertices in V I . We distinguish between three cases. In each case, our goal is to show that one codeword can be spared (contradiction with the optimality of C) or that several optimal codes are possible.

(i) r = 2. The two vertices on the stem of the unique diapason pasted on e both 2-cover u and v, so at most one of them is necessary in the code, and they are interchangeable.

(ii) r ≥ 4. (a) All the feet of the r -1 diapasons r-cover u and v, so at most one of them is necessary in the code, and they are interchangeable. (b) If, say, u is linked to t 1,1 and v to t r-1,1 , then

so there are at least two vertices on the first stem which r-cover u, not v, at most one of them is necessary in the code, and they are interchangeable. The same is true by symmetry for t r-1,r and t r-1,r-1 .

(iii) r = 3. (a) The feet of the two diapasons 3-cover u and v, and the conclusion is the same as previously. (b) Without loss of generality, we assume that we are in the following case: the codeword is t 1,3 ; it is the only vertex in Ω which 3-covers u, not v, so it 3-separates these two vertices. If u = A j for some j ∈ {1, 2, . . . , m}, then it is 3-covered and 3-separated from v by the shortened diapason, and t 1,3 can be spared. So u is one of the six vertices in V i for some i ∈ {1, 2, . . . , n}. If u ∈ {x i , x i , b i , d i }, that is, if u has degree at least two in G I , then we can replace t 1,3 by another vertex suitably chosen in a diapason pasted on another edge incident to u in G I . So we are left with the case when, say, u = a i , and so v = b i . But b i is 3-covered by at least one codeword. (b1) This codeword also 3-covers a i . Then t 1,3 can be replaced in C by a vertex 3-covering b i , not a i : this choice also allows to have a i and b i 3-covered and 3-separated by C. (b2) The codeword 3-covering b i does not 3-cover a i . Then t 1,3 can be replaced in C by, e.g., t 1,2 , because a i and b i are already 3-separated by C.

So in all cases, we have at least two possible optimal codes, and we can assume from now on that each copy of Ω contains exactly (r -1)(2r + 2) codewords, and each copy of ∆ -exactly 2r + 2 codewords.

The case when there are four (or more) codewords in a component G i can be treated exactly like the case r = 1, as if the copies of Ω did not exist. This is also true if each G i has exactly three codewords, and one extra codeword is on some A j , because then A j r-covers some x i or x i . In all cases, there is more than one possibility for V i ∩ C.

In conclusion, whenever there are more than k codewords in an optimal code, there are several possible optimal codes, and the answer to U-OIdC r is NO.

♦

Corollary 32 Let r ≥ 1 be any integer. The decision problems U-IdC r and U-OIdC r are NP-hard. ♦ Proposition 33 Let r ≥ 2 and q ≥ 1 be any integers. There is a polynomial reduction from U-IdC qr to U-IdC q and from U-OIdC qr to U-OIdC q : U-IdC qr → p U-IdC q and U-OIdC qr → p U-OIdC q . As a particular case, we have U-IdC r → p U-IdC 1 and U-OIdC r → p U-OIdC 1 .

Proof. See the proof of Proposition 18 and Lemma 5(b). ♦

An Upper Bound for the Complexity of U-IdC r

Theorem 34 There exists a polynomial reduction from U-IdC 1 to U-SAT: U-IdC 1 → p U-SAT.

Proof. We refer to the proof of Theorem 19, and we give here only the clauses that describe the identification problem. These clauses are constructed in the following way: (a1) for each vertex x i ∈ V with neighbours x n 1 , . . . , x ns , we take the clause of size k(s + 1):

x n 1 2 , . . . , x n 1 k , x n 2 1 , . . . , x n 2 k , . . . , x ns 1 , . . . , x ns k };

(a2) for each pair of vertices x i ∈ V , x j ∈ V , we consider the set B 1 (x i ) ∆B 1 (x j ) = {x h 1 , x h 2 , . . . , x h ℓ }; by the assumption that G is 1-twin-free, we have ℓ > 0. Then we simply take the clause

which is the second part of the clause c x i x j in the aforementioned proof.

Then the argument goes exactly like for Theorem 19, in particular thanks to the characterization given by (1). ♦ By Proposition 33 or its corollary, this immediately implies that there is a polynomial reduction from U-IdC r to U-SAT.

Theorem 35 Let r ≥ 1 be any integer. The problem U-IdC r has complexity equivalent to that of U-SAT. As a consequence, U-IdC r belongs to the class DP. ♦