Some Complexity Considerations on the Uniqueness of Graph Colouring

Abstract: For some well-known N P-complete problems, linked to the colourability of a graph, we study the

variation which consists in asking about the uniqueness of a solution (up to permutations of the colours). In

particular, we show that the decision problems Unique k-Colouring (U-k-COL) with k>3and Unique Colouring

(U-COL), have equivalent complexities, up to polynomials, as Unique Satisﬁability (U-SAT) and Unique One-

in-Three Satisﬁability (U-1-3-SAT) by establishing polynomial reductions relating these four problems. As a

consequence, all are co-N P-hard (or, equivalently, N P-hard with respect to Turing reductions) and belong to

the complexity class DP. We also consider the problem Unique Optimal Colouring (U-OCOL) and show that it

belongs to LN P (also denoted Θ2).

Key-Words: Complexity Theory, co-N P-hardness, N P-hardness, Decision Problems, Polynomial Reduction,

Turing Reduction, Uniqueness of Solution, Graph Theory, Graph Colouring, Partition into Independent Sets,

Boolean Satisﬁability, Satisﬁability Problems.

Received: November 14, 2022. Revised: May 13, 2023. Accepted: June 7, 2023. Published: July 5, 2023.

1 Introduction

1.1 Goal, Outline and Results

In the theory of complexity, decision problems are

stated with a question that admits only the answer

YES or NO; the question can be stated in the very

general following form: “Given an instance Iand

a property P r on I, is P r true for I?” where P r

can be expressed as: “Is there a structure satisfying

a given characteristic?”. In our study, we add the

extra word “unique” to the latter question: “Is there

aunique structure satisfying a given characteristic?”

Then we investigate the complexity of these newly

deﬁned problems. In this paper, we pay attention

to the uniqueness of the vertex-colouration of graphs

(up to colour permutations). For this, we consider

the uniqueness for some variations of the well-known

problem SAT.

In Section 1.2, we give some notation and deﬁni-

tions from graph theory and then, in Section 1.3, the

basic background for the complexity theory; in Sec-

tion 1.4, we present some well-known Satisﬁability

problems, together with their complexities. In Sec-

tion 2, we study how these complexities vary if we

consider the question of the uniqueness of a solution

for colouring problems. We prove that the colouring

problems called below U-k-COL (k>3) and U-COL

have equivalent complexities as U-SAT and U-1-3-

SAT; consequently, they all belong to the class DP

and are co-N P-hard (or, equivalently, N P-hard with

respect to Turing reductions). We also show that U-

OCOL belongs to the class LN P . We present some

concluding remarks in Section 3.

We similarly revisited some famous problems,

from the viewpoint of uniqueness of solution: Vertex

Cover and Dominating Set (as well as its generaliza-

tion to domination within distance r) [17], Hamilto-

nian Cycle [18], and r-Identifying Code together with

r-Locating-Dominating Code [16].

Note that uniqueness of solutions, which may

be seen as part of the wider issue of the number

of solutions of a problem, had been studied earlier

in a few papers (see, e.g., [3], [4], [5], [9], [12],

[13], [20], [21], [22], [27]). In particular, the com-

plexity of the uniqueness for SAT problems has been

studied in [20], which provides a “dichotomy theo-

rem” characterizing the variants of SAT for which the

uniqueness is polynomial.

1.2 Notation and Deﬁnitions for Graphs

For graph theory, we refer to, e.g., [2] or [8]. We

shall denote by G= (V, E)a ﬁnite, simple, undi-

rected graph with vertex set Vand edge set E, where

an edge between x∈Vand y∈Vis indifferently

denoted by xy or yx. The order of the graph is its

number of vertices.

An independent set, or stable set, is a subset

V∗⊆Vsuch that for all u∈V∗,v∈V∗,uv is

not an edge of G:uv /∈E. If kis an integer, k>1, a

k-colouring of Gis a function f:V→ {1,2, . . . , k}

such that f(u)6=f(v)whenever uv ∈E. Two ver-

tices with the same value on the function fare said

to share the same colour. Obviously, a k-colouring

of Gexists if and only if one can partition Vinto

kindependent sets, with a correspondence between

an independent set and a set of vertices sharing the

1OLIVIER HUDRY, 2ANTOINE LOBSTEIN

1Institut polytechnique de Paris, T´el´ecom Paris, 91123 Palaiseau

2Laboratoire Interdisciplinaire des Sciences du Num´erique

(UMR 9015), CNRS, Universit´e Paris-Saclay, 91400 Orsay

FRANCE

WSEAS TRANSACTIONS on MATHEMATICS

DOI: 10.37394/23206.2023.22.54

Olivier Hudry, Antoine Lobstein

E-ISSN: 2224-2880

483

Volume 22, 2023

same colour. When it exists, such a partition of V

will be called a k-IS-partition. Since fewer than k

colours may be needed, we might be led to use the

word “partition” in a sense broader than usual, with

empty sets allowed. The smallest ksuch that there is

ak-IS-partition is called the chromatic number χ(G)

of G. A colouring with a number of colours equal to

χ(G)is said to be optimal.

1.3 Notation and Deﬁnitions for Complexity

We expound here the notions of complexity that will

be needed in the sequel. We refer the reader to, e.g.,

[1], [10], [19] or [23] for more on this topic. Here, we

consider complexity only with respect to computing

time and not with respect to memory space.

Adecision problem is of the type “Given an ins-

tance Iand a property P r on I, is P r true for I?”,

and has only two solutions, YES or NO. The com-

plexity class Pdenotes the set of problems which

can be solved by a polynomial (time) algorithm, and

the complexity class N P the set of problems which

can be solved by a nondeterministic polynomial algo-

rithm.

Apolynomial reduction from a decision pro-

blem π1to a decision problem π2is a polynomial

algorithm that maps any instance of π1into an equiva-

lent instance of π2, that is, an instance of π2admitting

the same answer as the instance of π1; in this case,

we write π16p

mπ2, or simply π16π2. Cook [6]

proved that there is a problem in N P, namely “Satis-

ﬁability” or simply SAT (see below in Section 1.4),

to which every other problem in N P can be polyno-

mially reduced. Thus, in a sense, SAT is a “hardest”

problem inside N P. Other problems share this pro-

perty in N P and are called N P-complete problems;

their class is denoted by N P-complete or N P-C.

The way to show that a decision problem πis

N P-complete is, once it is proved to be in N P, to

choose some N P-complete problem and to polyno-

mially reduce it to π. From a practical viewpoint, the

N P-completeness of a problem πimplies that we do

not know any polynomial algorithm solving π, and

that, under the assumption P 6=N P, which is widely

believed to be true, no such algorithm exists: the

time required can grow exponentially with the size

of the instance (for example, when the instance is a

graph, its size is polynomially linked to the order of

the graph; see below, Section 2).

The complement of a decision problem, “Given I

and P r, is P r true for I?”, is “Given Iand P r, is

P r false for I?”. The class co-N P (respectively, co-

N P-complete or co-N P-C) is the class of the pro-

blems which are the complement of a problem in N P

(respectively, in N P-C).

For problems which are not necessarily decision

problems, a Turing reduction from a problem π1to

a problem π2is an algorithm Athat solves π1using

a (hypothetical) subprogram Ssolving π2such that,

if Swere a polynomial algorithm for π2, then A

would be a polynomial algorithm for π1; in this case,

we write π16Tπ2. Thus, in this sense, π2is “at

least as hard” as π1. A problem πis N P-hard (res-

pectively, co-N P-hard) if there is a Turing reduc-

tion from some N P-complete (respectively, co-N P-

complete) problem to π[10, p. 113].

Remark 1 Note that with these deﬁnitions, N P-

hard and co-N P-hard coincide [10, p. 114].

The notions of completeness and hardness can of

course be extended to classes other than N P or co-

N P. Note that N P-hardness and co-N P-hardness

are deﬁned differently in [7] and [15] for instance:

there, a problem πis N P-hard (respectively, co-

N P-hard) if there is a polynomial reduction from

some N P-complete (respectively, co-N P-complete)

problem to π; then, with these deﬁnitions, N P-

hardness and co-N P-hardness do not coincide any

more and this may lead to confusion (see Section 3).

For the problems studied here, our results show that

U-k-COL (k>3) and U-COL are co-N P-hard for

both polynomial and Turing reductions, while they

are N P-hard only for Turing reductions.

We will use two more classes. They received dif-

ferent notations, or were shown to be the same as

classes deﬁned differently, hence the multiple nota-

tions (see, e.g., [14]).

•The class LN P [19] contains the decision problems

which can be solved by applying, with a number of

calls which is logarithmic with respect to the size of

the instance, a subprogram able to solve an appro-

priate problem in N P (usually, an N P-complete

problem). It is also denoted by PN P[O(log n)], or

PN P[log], or Θ2, or ΘP

2, or still P||N P ; in the sequel,

we will use the notation LN P , easier to remember.

This class should not be confused with the class L,

which is the class of decision problems solvable by

a Turing machine restricted to use an amount of me-

mory logarithmic in the size of the input.

•Finally, let us deﬁne DP [25] (or DIFP[3] or

BH2[19], [28], . . .) as the class of languages (or

problems) Lsuch that there are two languages L1∈

N P and L2∈co-N P satisfying L=L1∩L2. This

class is not to be confused with N P ∩ co-N P (see

the warning in, e.g., [23, p. 412]); actually, DP con-

tains N P ∪ co-N P and is contained in LN P (see

Figure 1).

Membership to P,N P, co-N P,DP, or LN P

gives an upper bound on the complexity of a problem

(this problem is not more difﬁcult than . . .), whereas

a hardness result gives a lower bound (this problem

WSEAS TRANSACTIONS on MATHEMATICS

DOI: 10.37394/23206.2023.22.54

Olivier Hudry, Antoine Lobstein

E-ISSN: 2224-2880

484

Volume 22, 2023

is at least as difﬁcult as . . .). Still, such results are

conditional in some sense; if for example P=N P,

they would lose their interest.

1.4 Satisﬁability Problems

We ﬁrst recall some problems related to Boolean

Satisﬁability, and present what is known about their

complexities.

We consider a set Xof nBoolean variables

xi(16i6n). A literal is a variable xor

its complement (or negated variable) x; let Xde-

note the set of the complement variables of X:

X={xwith x∈ X }. A clause deﬁned on Xis a

subset of X ∪ X . We consider a set Cof mclauses

cj(16j6m); Cis also called a Boolean formula.

Each clause cjcontains κjliterals. Equivalently, C

can read as a logical formula:

C=∧16j6mcj,with cj=∨16i6κj`j

with `j

i∈ X ∪ X for 16j6mand 16i6κj.

This form is called a normal conjunctive form. A

truth assignment for Xsets the variable xito TRUE,

also denoted by T, and its complement to FALSE

(or F), or vice-versa. A truth assignment is said to

satisfy the clause cjif cjcontains at least one true lite-

ral, and to satisfy the set of clauses Cif every clause

contains at least one true literal. The following deci-

sion problems, for which the size of the instance is

polynomially linked to n+m, are classical problems

in complexity.

Problem SAT (Satisﬁability):

Instance: A set Xof variables, a collection Cof

clauses over X.

Question: Is there a truth assignment for Xthat satis-

ﬁes C?

Problem 1-3-SAT (One-in-Three Satisﬁability):

Instance: A set Xof variables, a collection Cof

clauses over X, each clause containing exactly three

different literals.

Question: Is there a truth assignment for Xsuch that

each clause of Ccontains exactly one true literal?

We shall say that a clause (respectively, a set

of clauses) is 1-3-satisﬁed by an assignment if this

clause (respectively, every clause in the set) contains

exactly one true literal.

Problem SAT (co-Satisﬁability):

Instance: A set Xof variables, a collection Cof

clauses over X.

Question: Is it true that no truth assignment for X

satisﬁes C?

The problem SAT is one of the basic and most

well-known N P-complete problems [6], [10, p. 39

and p. 259]. It follows that the problem SAT is co-

N P-complete.

The problem 1-3-SAT is also N P-complete [26,

Lemma 3.5], [10, p. 259].

The problems U-SAT and U-1-3-SAT are obtained

from the above problems SAT and 1-3-SAT respec-

tively by adding the word “unique” in the question.

The problem U-SAT has been studied as far back as

1982 ([3], [24]). The problems U-SAT and U-1-3-

SAT share the same complexity. More precisely, we

have:

U-SAT 6U-1-3-SAT 6U-SAT.(1)

They are both N P-hard and both belong to DP.

Remark 2 In [23], it is stated that “U-SAT is not

believed to be DP–complete”. It is shown in [3]

that there exists one oracle under which U-SAT is not

DP–complete; and one oracle under which it is, if

N P and co-N P are distinct.

2 Uniqueness for Colouring Problems

We now turn to the colouring decision problems,

stated in their two usual forms. First, for a given inte-

ger k>1:

Problem k-COL (k-Colouring):

Instance: A graph G.

Question: Does Gadmit a k-colouring?

It is well known that this problem is trivial for

k= 1, polynomial for k= 2 and N P-complete for

k>3, see [11], [10, p. 191]. We can also state the

problem COL with kbelonging to the instance:

Problem COL (Colouring):

Instance: A graph G, an integer k.

Question: Does Gadmit a k-colouring?

The problem COL is also N P-complete.

In their spirit, the problems U-k-COL and U-COL

are derived from the above problems k-COL and

COL respectively in a similar manner as previously

done for satisﬁability problems.

Anyway, if we deﬁne the problem of the existence

of a unique k-colouring in a graph by simply adding

the word “unique” in the statements of the problems

k-COL or COL, it is quite obvious that the answer

will always be NO for k > 1, since any permutation

(other than the identity) on the values of a k-colouring

provides another k-colouring. So, rather than saying

that we look for a unique colouring up to permuta-

tions, it is more relevant to consider the problems

stated in terms of IS-partitions. Also, if the graph

is not connected, the answer will be NO for k > 1.

Thus, the problems that we study assume the graphs

to be connected, as stated below:

WSEAS TRANSACTIONS on MATHEMATICS

DOI: 10.37394/23206.2023.22.54

Olivier Hudry, Antoine Lobstein

E-ISSN: 2224-2880

485

Volume 22, 2023

Let kbe a ﬁxed integer with k>1.

Problem U-k-COL (Unique k-IS-Partition):

Instance: Aconnected graph G.

Question: Does Gadmit a unique k-IS-partition?

Problem U-COL (Unique IS-Partition):

Instance: Aconnected graph G, an integer k.

Question: Does Gadmit a unique k-IS-partition?

We add the following problem, which would be

irrelevant without the word “unique” in its question,

and which will be dealt with in Section 2.3:

Problem U-OCOL (Unique Optimal IS-Partition):

Instance: Aconnected graph G= (V, E).

Question: Is there a unique way of partitioning V

into a minimum number of independent sets?

Note that, like 1-COL and 2-COL, U-1-COL and

U-2-COL are, quite obviously, polynomial.

As the graphs are assumed to be connected, we

may assume also, without loss of generality, that they

are encoded by their adjacency matrices. Thus, the

size of a graph Gwith nvertices is equal to n2.

2.1 Preliminary Results on 3-Colourings

The following lemma is somehow inspired by the

proof of the N P-completeness of 3-COL, see Theo-

rem 2.1 and Figure 1 in [11]. Note that the proof

from [11] cannot convey uniqueness, even up to per-

mutations of colours.

Lemma 3 Consider the graph G0= (V0, E0)des-

cribed by Figure 2.

(a) Any 3-IS-partition of {a, b, d}such that these

three vertices belong to the same independent set,

cannot be extended to a 3-IS-partition in G0.

(b) Any 3-IS-partition of {a, b, d}such that these

three vertices belong to exactly two independent sets,

can be uniquely extended to a 3-IS-partition in G0.

Proof. Without loss of generality, we assume that in

any 3-IS-partition of V0into S1, S2, S3, the vertex v2

belongs to S3. Then a,band dcan belong only to S1

or S2.

(a) First, we assume that the vertices a,band d

belong to S1. Then, because of the triangle a, w1, v2,

we have w1∈S2. Similarly, z2∈S2,z3∈S2.

Then z1∈S3, and step by step, w2∈S1,w3∈S3,

v1∈S2,w4∈S1,y6∈S2,y2∈S3,y1∈S2,

y4∈S1, and y5∈S3. But now the neighbours of y3

are y6∈S2,y5∈S3and d∈S1, which makes

it impossible to have a 3-IS-partition. Obviously, the

conclusion is the same if a,band dbelong to S2, with

the roles of S1and S2permuted.

(b) Assume ﬁrst that a∈S1,b∈S1,d∈S2.

Then {w1, z2} ⊂ S2,z3∈S1,z1∈S3,w2∈S1,

v1∈S2,w3∈S3,w4∈S1,y6∈S2,y2∈S3,

y1∈S2,y4∈S1,y5∈S3and y3∈S1, which

constitutes a 3-IS-partition, obtained in a unique way.

The same is true for a∈S2,b∈S2,d∈S1, with the

roles of S1and S2permuted.

For a∈S1,b∈S2,d∈S1, we simply give the

three sets S1,S2and S3, since it is straightforward

to check that there is only one way to obtain them:

S1={a, d, z2, w3, w4, y5, y2},S2={b, z1, z3, w1,

v1, y6, y4},S3={v2, w2, y3, y1}. The case with

a∈S2,b∈S1,d∈S2is the same, with the roles

of S1and S2permuted.

For a∈S2,b∈S1,d∈S1, the partition

S1={b, d, w1, w3, z1, w4, y5, y1},S2={a, z2, z3,

v1, y6, y4},S3={v2, w2, y3, y2}is the only 3-IS-

partition. The case with a∈S1,b∈S2,d∈S2is

the same, with the roles of S1and S2permuted. 4

Remark 4 We can see from the previous proof that

w4, which is linked to v1and v2, belongs to S1as

soon as two of the three vertices a, b, d belong to S1

— and w4∈S2if two of a, b, d belong to S2. This

implies that v1∈S2in the ﬁrst case, v1∈S1in the

latter case.

We are now ready to show that U-SAT and U-COL

have equivalent complexities (up to polynomials).

2.2 Equivalence of Uniqueness of Colouring

and of Satisﬁability

We are going to prove the following polynomial

reductions:

•U-1-3-SAT 6U-3-COL (Theorem 5),

•for k>3, U-3-COL 6U-k-COL 6U-COL

(Proposition 6),

•and U-COL 6U-SAT (Theorem 7).

Theorem 5 There exists a polynomial reduction from

U-1-3-SAT to U-3-COL: U-1-3-SAT 6U-3-COL.

Proof. Consider an instance of U-1-3-SAT consis-

ting in a set Cof mclauses over nvariables xi

(16i6n). We associate to it an instance of U-3-

COL, i.e. a graph G, as follows. The vertex set Wof

Gis deﬁned by:

W={xi,xi: 1 6i6n}∪{v1, v2}

∪ {zi,j : 1 6i63,16j6m}

∪ {wi,j : 1 6i64,16j6m}

∪ {yi,j : 1 6i66,16j6m}.

The order of Gis 2n+ 2 + 13m. For every jin

{1, . . . , m}, we denote by V−

jthe set

V−

j={zi,j : 1 6i63}

∪ {wi,j : 1 6i64}

∪ {yi,j : 1 6i66},

WSEAS TRANSACTIONS on MATHEMATICS

DOI: 10.37394/23206.2023.22.54

Olivier Hudry, Antoine Lobstein

E-ISSN: 2224-2880

486

Volume 22, 2023

and by Vjthe set

Vj=V−

j∪ {v1,j , v2,j }.

For each clause cj={aj, bj, dj}(1 6j6m)

where aj, bjand djbelong to {xi, xi: 1 6i6n},

we take a copy Gj= (Vj∪ {aj, bj, dj}, Ej)of the

graph G0= (V0, E0)from the previous lemma, with

aj=a,bj=b,dj=d, and complete identiﬁcation

of the other vertices of V0to the vertices of Vj. Then

we merge all the vertices v1,j ,16j6m, into one

vertex v1, i.e., the new vertex v1replaces the v1,j ’s

and is linked to all their neighbours; we proceed simi-

larly to create a new vertex v2. The vertices v1and

v2are now common for all the clauses cjand sub-

graphs Gj— we still call these subgraphs Gj, with a

slight notational abuse.

We add the edges xixi,xiv2and xiv2,16i6n,

and we have our graph G; see Figure 3 for a small

example.

Let us now show that the answer is the same for

the initial instance of U-1-3-SAT and the instance of

U-3-COL.

(1) Let us ﬁrst assume that the answer to U-1-3-

SAT is YES: there is a unique truth assignment 1-3-

satisfying the clauses of C. We construct a valid 3-

IS-partition W=S1∪S2∪S3in the following way:

we put v2in S3, we put in S2the literals that have the

assignment TRUE, and in S1those which are FALSE.

Since each clause contains exactly one true literal, we

are in condition (b) of Lemma 3, and from now on,

there is a unique way for obtaining a 3-IS-partition

of W, by proceeding in each graph Gjas in the proof

of the lemma for V0: note that we cannot proceed

independently in each graph Gj, which could lead to

more than one partition, because of the vertices v1

and v2which are shared by all the graphs Gj.

Can we have another 3-IS-partition

W=S∗

1∪S∗

2∪S∗

3? Still assuming, without

loss of generality, that v2∈S∗

3, this 3-IS-partition,

like every 3-IS-partition in G, induces, because of

the triangles xixiv2, a valid truth assignment Afor

the variables xi,16i6n, by setting A(xi) = T

if xi∈S∗

2and A(xi) = F if xi∈S∗

1. If we study,

in a subgraph Gj0, the vertices aj0,bj0and dj0, we

know, by Lemma 3(a), that they cannot all belong to

the same set, S∗

1or S∗

2. If two of them belong to S∗

then, by Remark 4, w4,j0∈S∗

1and v1∈S∗

2. This in

turn implies that all the vertices w4,j ,16j6m,

belong to S∗

1, and then that, for all j, two among the

three vertices aj,bjand djbelong to S∗

1. Similarly,

if two of aj0,bj0and dj0belong to S∗

2, then for all j,

two of aj,bjand djbelong to S∗

2. Therefore, the

assignment Ais such that (a) in all the clauses, two

of the three vertices aj, bj, djbelong to S∗

1, or (b) in

all the clauses, two of the three vertices aj, bj, dj

belong to S∗

2. This proves that the assignment A, or

its complement, 1-3-satisﬁes all the clauses. Since

such an assignment was assumed to be unique, the

3-IS-partition W=S∗

1∪S∗

2∪S∗

3is the same as

W=S1∪S2∪S3.

Thus a YES answer to U-1-3-SAT implies a YES

answer to U-3-COL.

(2) Assume next that the answer to U-1-3-SAT is

NO: this may be either because no truth assignment

1-3-satisﬁes the instance, or because at least two as-

signments do; in the latter case however, this would

lead to at least two 3-IS-partitions, and a NO answer

to U-3-COL. So we are left with the case when the

set of clauses Ccannot be 1-3-satisﬁed. But if a

3-IS-partition of Wexists, then we have seen, with

S∗

1∪S∗

2∪S∗

3above, how to construct an assignment

which 1-3-satisﬁes all the clauses; therefore, no 3-IS-

partition can exist.

We have proved that, in all cases, the answer to

U-3-COL is also NO.

Thus the answer is the same for the two instances.

Moreover, the complexity of the reduction is di-

rectly linked to the size of G. Since the order of G

is 2n+ 13m+ 2, the size of Gis in O((n+m)2)

while the size of the instance of U-1-3-SAT is at least

n+m. So the reduction is polynomial.

In conclusion, we have what we wanted:

U-1-3-SAT 6U-3-COL. 4

Reducing U-3-COL into U-k-COL for k>4and

then U-k-COL for k>3to U-COL is much easier,

as shown by Proposition 6:

Proposition 6 For every integer k>3, there exists a

polynomial reduction from U-3-COL to U-k-COL: U-

3-COL 6U-k-COL, and from U-k-COL to U-COL:

U-k-COL 6U-COL.

Proof. To go from U-`-COL to U-(`+ 1)-COL for

any integer `, the trick is standard: a graph Gad-

mits a (unique) `-IS-partition if and only if the graph

obtained from Gby adding, in polynomial time, one

vertex connected to all the vertices of G, admits a

(unique) (`+ 1)-IS-partition. Starting from `= 3,

we can reach any ﬁxed k>3.

The problem U-COL, where k, the number of

colours, is not ﬁxed but is part of the instance, is at

least as hard as U-k-COL, for any ﬁxed integer k:

to any instance Gof U-k-COL, we can associate the

instance consisting of Gand kfor U-COL, also in

polynomial time. 4

When dealing with the usual problems like COL

and SAT, it is not necessary to establish the reduction

from COL to SAT explicitly: the belonging of COL to

N P and the N P-completeness of SAT are sufﬁcient

WSEAS TRANSACTIONS on MATHEMATICS

DOI: 10.37394/23206.2023.22.54

Olivier Hudry, Antoine Lobstein

E-ISSN: 2224-2880

487

Volume 22, 2023

to involve that such a reduction does exist. In other

words, because SAT is known to be N P-complete,

the properties COL ∈ N P and SAT 6COL are suf-

ﬁcient to show that SAT and COL belong to the same

complexity class, namely N P-C. For U-COL and U-

SAT, it is not sufﬁcient to reduce U-SAT to U-COL to

be able to conclude that these two problems have the

same complexity: we may only conclude from such a

reduction that U-COL is at least as difﬁcult as U-SAT.

So, in order to have the reciprocal statement, we now

reduce U-COL into U-SAT polynomially.

Theorem 7 There exists a polynomial reduction from

U-COL to U-SAT: U-COL 6U-SAT.

Proof. We start from an instance of U-COL, ie. a

connected graph G= (V, E)and an integer k, with

V={x1, . . . , x|V|}(where |V|denotes the order of

G); we assume that k>3and |V|>3. We create the

set of variables X={xh

i: 1 6h6|V|,16i6k}

and the following clauses:

(0) {x1

1};

(i) for 16h6|V|, clauses of size k:

{xh

1, xh

2, . . . , xh

k};

(ii) for 16h6|V|and 16i < j 6k, clauses

of size two: {xh

i, xh

j};

(iii) for every edge xhxh0∈E,kclauses of

size two: {xh

1, xh0

1},{xh

2, xh0

2},. . .,{xh

k−1, xh0

k−1},

{xh

k, xh0

k};

(iv) for 26h6|V|and 16i6k, clauses

We shall say that {xh

i}is the ﬁrst part

of ch

i,{x1

i, . . . , xh−1

i}its second part, and

{x1

i−1, . . . , xh−1

i−1}its third part. When i= 1,

ireduces to its ﬁrst and second parts. All these

clauses form the instance of U-SAT.

The role of the variables and of the clauses will

appear below in the proof.

Note that the number of variables and clauses is

polynomial with respect to the order of G, in particu-

lar because we may take k6|V|. As the complexity

of the reduction is polynomially related to this num-

ber of variables and clauses, the reduction is polyno-

mial.

Let us show now that the answer is kept by the

reduction.

(1) We assume that there is a k-IS-partition of Vinto

ksets S1, S2, . . . , Sk. If necessary, we redeﬁne this

partition, with renamed sets S∗

1,S∗

2, . . . , S∗

k, in the

following way: we put x1in S∗

1; then if x2was in the

same set as x1, we also put x2in S∗

1, otherwise we

put it in S∗

2; more generally, if xpwas in the same set

as some xq,q < p, we put xpin the same set as xq,

otherwise we put it in S∗

t, where tis the smallest in-

dex that has not been used yet for a set S∗; and so

on, until we have processed all the vertices. In other

words, we re-order the sets S1,S2,. . . , Skaccording

to the order of the smallest superscript of their ele-

ments. In particular, x1belongs to the ﬁrst set.

Example. k= 5,|V|= 14,S1={x5, x2, x8},

S2={x3, x14, x4},S3={x10, x1, x12},S4={x7,

x9, x11},S5={x13, x6}.After re-ordering as

described above, we have S∗

1={x1, x10, x12},

S∗

2={x2,x5, x8},S∗

3={x3, x4, x14}, S∗

4={x6,

x13},S∗

5={x7, x9, x11}.

If we have a k-IS-partition S1,S2,. . . , Skordered as

above, we can deﬁne a truth assignment A1by set-

ting, for every variable xh

i,A1(xh

i) = T if and only if

xh∈Si, and this assignment satisﬁes all the clauses;

indeed:

(0) {x1

1}is satisﬁed thanks to the re-ordering;

(i) each clause {xh

1, xh

2, . . . , xh

k}contains at least

one true literal, the contrary meaning that the ver-

tex xhbelongs to no set of the k-IS-partition;

(ii) each clause {xh

i, xh

j}contains at least one true

literal, the contrary meaning that the vertex xhbe-

longs to two sets Siand Sj;

(iii) each clause {xh

i, xh0

i}contains at least one

true literal, the contrary meaning that two neighbours

in Gbelong to the same set Si;

(iv) let us consider ch

ifor given hand i,

26h6|V|,16i6k, and assume that it

is not satisﬁed by A1. Then the ﬁrst part

of ch

iimplies that xh∈Si, the second part that

{x1, . . . , xh−1} ∩ Si=∅; if i= 1, this is impossi-

ble, since x1∈S1. So i > 1and ch

ihas a third

part, which, when not satisﬁed, implies that

{x1, . . . , xh−1} ∩ Si−1=∅. But then xhshould

have been put in Si−1(or possibly even earlier) when

re-ordering the k-IS-partition, and we have a con-

tradiction. Therefore, all the clauses ch

iare satisﬁed

by A1. We can conclude that any k-IS-partition

gives a truth assignment satisfying all the clauses

constructed for U-SAT.

Assume now that this k-IS-partition is unique, i.e.,

we have a YES answer for U-COL. We claim that

there is only one assignment satisfying the instance

of U-SAT. Assume on the contrary that another as-

signment, A2, also satisﬁes it. Then, thanks to the

clauses described in (i) and (ii), for every h, at least

one literal xh

iis set TRUE by A2, and for every pair

{i, j},i6=j, at least one of xh

ior xh

jis set TRUE,

which means that at most one xh

iis set TRUE: so for

every h,exactly one xh

iis TRUE. Using this, let us

construct a partition S+

1, . . . , S+

kusing the following

rule: xh∈S+

iif and only if A2(xh

i) = T.

WSEAS TRANSACTIONS on MATHEMATICS

DOI: 10.37394/23206.2023.22.54

Olivier Hudry, Antoine Lobstein

E-ISSN: 2224-2880

488

Volume 22, 2023

Now because of the clauses {xh

i, xh0

i}correspon-

ding to neighbours xhand xh0in G, at least one of

ior xh0

iis set FALSE by A2: this means that two

neighbours cannot be in the same set and guarantees

that the partition S+

1, . . . , S+

kis a k-IS-partition of V,

and, by assumption, it must coincide with S1,S2,

. . . , Sk,up to permutations of the subscripts. This is

where the clauses introduced in Step (iv) intervene:

without them, a single k-IS-partition could give more

than one assignment, differing only according to the

permutations on the subscripts of the sets of the k-IS-

partition.

We are going to prove that S1=S+

1,S2=S+

. . .,Sk=S+

k. Because of the clause {x1

1}, we have

A2(x1

1) = T, implying that x1∈S+

1and S1=S+

Now assume that there are two sets S+

pand S+

qsuch

that 1< p, q =p+ 1, and the element with smal-

lest superscript in S+

p,xp1, has superscript greater

than the element with smallest superscript in S+

q,xq1:

p1> q1. Consider the clause

cq1

q=cq1

p+1

={xq1

p+1, x1

p+1, . . . , xq1−1

p+1 , x1

p, . . . , xq1−1

p}.

Now A2(xq1

p+1) = T, and none of the vertices

x1, . . . , xq1−1, which all have superscripts smaller

than q1and p1, can belong to S+

q=S+

p+1 nor

to S+

p. This implies that cq1

qcannot be satisﬁed by A2,

a contradiction. It follows that the k-IS-partition

S+

1, . . . , S+

kis ordered according to the smallest

superscript of the elements in its sets, i.e., it has the

same set order as the k-IS-partition S1, . . . , Sk, which

was our claim, and consequently A1=A2, i.e., we

have also a YES answer to U-SAT.

Example. Let Gbe a triangle: k= 3, G = (V, E)

with V={x1, x2, x3}, E ={x1x2, x1x3, x2x3}.

The clauses are:

(0) {x1

1};

(i) {x1

1, x1

2, x1

3},{x2

1, x2

2, x2

3},and {x3

1, x3

2, x3

3};

(ii) {x1

1, x1

2},{x1

1, x1

3},{x1

2, x1

3},{x2

1, x2

2},{x2

1, x2

3},

{x2

2, x2

3},{x3

1, x3

2},{x3

1, x3

3},and {x3

2, x3

3};

(iii) {x1

1, x2

1},{x1

2, x2

2},{x1

3, x2

3},{x1

1, x3

1},{x1

2, x3

2},

{x1

3, x3

3},{x2

1, x3

1},{x2

2, x3

2},and {x2

3, x3

3}.

If we stop here, two assignments A1,A2are pos-

sible, one corresponding to x1∈S1,x2∈S2,

x3∈S3:A1(x1

1) = A1(x2

2) = A1(x3

3) = T,

A1(x1

2) = A1(x1

3) = A1(x2

1) = A1(x2

3) =

A1(x3

1) = A1(x3

2) = F, the other corresponding

to x1∈S1,x2∈S3,x3∈S2:A2(x1

1) =

A2(x2

3) = A2(x3

2) = T,A2(x1

2) = A2(x1

3) =

A2(x2

1) = A2(x2

2) = A2(x3

1) = A2(x3

3) = F. How-

ever, only A1satisﬁes the clauses (iv), which are:

1={x2

1,x1

1},c3

1={x3

1, x1

1, x2

1},c2

2={x2

2,x1

1},

2={x3

2,x1

2,x2

2,x1

1,x2

1},c2

3={x2

3,x1

2},and

3={x3

3, x1

3, x2

3, x1

2, x2

2}.Indeed, c2

3is not satisﬁed

by A2.

(2) Assume now that the answer to U-COL is nega-

tive. If it is negative because there are at least two

k-IS-partitions of V, then we have at least two as-

signments satisfying the instance of U-SAT: we have

seen above how to construct a suitable assignment

from a k-IS-partition, and different partitions lead to

different assignments. If there is no k-IS-partition,

then there is no assignment satisfying U-SAT, be-

cause such an assignment would give a k-IS-partition,

as we have seen above in the proof with A2. So in

both cases, a NO answer to U-COL implies a NO ans-

wer to U-SAT.

In conclusion, the reduction saves the answer and

is polynomial: thus U-COL 6U-SAT. 4

As U-SAT and U-1-3-SAT have equivalent com-

plexities (see the relationship (1) above), we directly

obtain the conclusion stated by the following theorem

as a consequence of the transitivity of the relation 6

and of Theorem 5, Proposition 6 and Theorem 7:

Theorem 8 The problems U-SAT, U-1-3-SAT, U-k-

COL for every integer k>3and U-COL have equi-

valent complexities, up to polynomials. All are co-

N P-hard (and N P-hard by Remark 1) and belong

to the class DP.4

Note that it could have been shown directly that

U-k-COL (k>1) and U-COL belong to DP. In-

deed, for U-k-COL, we have to exhibit two languages

L1∈ N P and L2∈co-N P such that the set of YES

instances of U-k-COL is L1∩L2. To reach this aim,

it is sufﬁcient to deﬁne L1as {G: there is at least one

k-IS-partition in G}and L2as {G: there is at most

one k-IS-partition in G}. We can proceed similarly

for U-COL.

2.3 Location of U-OCOL

Proposition 9 below provides an upper bound on the

complexity of U-OCOL in the complexity classes

hierarchy.

Proposition 9 The problem U-OCOL belongs to the

class LN P .

Proof. Let us design an algorithm A2solving U-

OCOL based on an algorithm A1solving COL,

which belongs to N P, in such a way that the num-

ber of calls to A1is logarithmic with respect to the

size of the instance; for this, consider any instance

Iof U-OCOL: Iis deﬁned by a graph G. So, if n

denotes the order of G, the size |I|of Iis equal to n2.

WSEAS TRANSACTIONS on MATHEMATICS

DOI: 10.37394/23206.2023.22.54

Olivier Hudry, Antoine Lobstein

E-ISSN: 2224-2880

489

Volume 22, 2023

Step 1. Consider the instances of COL of the form

(G, k)where Gis the graph of Iand kan integer bet-

ween 1 and n. By applying a standard dichotomous

process on kbetween 1and n, we can build an algo-

rithm A2based on A1and outputting the chromatic

number χ(G)of G. In A2, the number of calls to A1

is about log2n, i.e. is upper-bounded by log2|I|.

So we may perform Step 1 with a logarithmic

number (with respect to |I|) of calls to an algorithm

solving a problem in N P.

Step 2. Once we have computed χ(G), we ques-

tion the instance (G, χ(G)) of U-COL, and we get

the answer to U-OCOL.

Since U-COL belongs to DP and because DP is

a subset of LN P , this step can also be performed with

a logarithmic number (with respect to |I|) of calls to

an algorithm solving a problem in N P.

Conclusion: all in all, by performing Step 1 and

then Step 2, we obtain an algorithm solving U-OCOL

with a logarithmic number of calls to an algorithm

solving a problem in N P, which is the deﬁnition of

the membership to U-OCOL to LN P .4

Note that using an algorithm for U-COL without

knowing the chromatic number leads nowhere, be-

cause a NO answer cannot be interpreted unambi-

guously: either kis smaller than the chromatic num-

ber, and there is no colouring, or kis greater than or

equal to the chromatic number, but there is more than

one colouring.

3 Conclusion

Theorem 8 states that the four problems U-SAT, U-1-

3-SAT, U-k-COL with k>3and U-COL are equi-

valent; they lie somewhere in the area of Figure 1

located below the DP line and above the N P-hard

dashed line; according to [23] (cf. Remark 2), they

are probably not DP-complete.

For the problem U-OCOL, we have a poorer result

(Proposition 9): U-OCOL belongs to LN P .

In [3], the authors wonder whether U-SAT is N P-

hard; but what they mean seems to be: “does there

exist a polynomial reduction from an N P-complete

problem to U-SAT?” i.e., they use the second deﬁ-

nition of N P-hardness, based on polynomial reduc-

tions (see the paragraph after Remark 1).

They show that this would be the case if and only

if U-SAT is DP-complete. Because of the results

stated in Theorem 8, the same applies to U-k-COL

for k>3and for U-COL.

This constitutes a part of the concluding open

problems.

Open problems.

1. Determine a better location for U-k-COL (k>3),

U-COL and U-OCOL in the classes of complexity.

2. Are U-k-COL (k>3) and U-COL DP-complete?

3. Is U-OCOL LN P -complete?

References:

[1] J.-P. BARTH ´

ELEMY, G. D. COHEN and

A. C. LOBSTEIN: Algorithmic Complexity and

Communication Problems, University College

of London: London, 1996.

[2] C. BERGE: Graphes, Gauthier-Villars: Paris,

1983. English translation: Graphs, North-

Holland Publishing Co.: Amsterdam, 1985.

[3] A. BLASS and Y. GUREVICH: On the unique

satisﬁability problem, Information and Control,

Vol. 55, pp. 80-88, 1982.

[4] M. BLIDIA, M. CHELLALI, R. LOUNES

and F. MAFFRAY: Characterizations of trees

with unique minimum locating-dominating sets,

Journal of Combinatorial Mathematics and

Combinatorial Computing, Vol. 76, pp. 225–

232, 2011.

[5] C. CALABRO, R. IMPAGLIAZZO, V. KA-

BANETS and R. PATURI: The complexity

of Unique k-SAT: an isolation lemma for k-

CNFs, Journal of Computer and System Scien-

ces, Vol. 74, pp. 386–393, 2008.

[6] S. A. COOK: The complexity of theorem-

proving procedures, Proceedings of 3rd An-

nual ACM Symposium on Theory of Computing,

pp. 151–158, 1971.

[7] T. CORMEN: Algorithmic complexity, in:

K. H. Rosen (ed.) Handbook of discrete and

combinatorial mathematics, pp. 1077–1085,

CRC Press: Boca Raton, 2000.

[8] R. DIESTEL: Graph Theory, Springer-Verlag:

Berlin, 2005.

[9] M. FISCHERMANN: Block graphs with unique

minimum dominating sets, Discrete Mathema-

tics, Vol. 240, pp. 247–251, 2001.

[10] M. R. GAREY and D. S. JOHNSON: Compu-

ters and Intractability, a Guide to the Theory of

NP-Completeness, Freeman: New York, 1979.

[11] M. R. GAREY, D. S. JOHNSON and

L. STOCKMEYER: Some simpliﬁed NP-

complete graph problems, Theoretical Com-

puter Science, Vol. 1(3), pp. 237–267, 1976.

[12] G. GUNTHER, B. HARTNELL, L. R. MAR-

KUS and D. RALL: Graphs with unique mini-

mum dominating sets, Congressus Numeran-

tium, Vol. 101, pp. 55–63, 1994.

WSEAS TRANSACTIONS on MATHEMATICS

DOI: 10.37394/23206.2023.22.54

Olivier Hudry, Antoine Lobstein

E-ISSN: 2224-2880

490

Volume 22, 2023

[13] P. HANSEN and B. JAUMARD: Uniquely sol-

vable quadratic Boolean equations, Discrete Ap-

plied Mathematics, Vol. 12(2), pp. 147-154,

1985.

[14] L. A. HEMACHANDRA: The strong exponen-

tial hierarchy collapses, Journal of Computer

and System Sciences, Vol. 39, pp. 299–322,

1989.

[15] L. HEMASPAANDRA: Complexity classes, in:

K. H. Rosen (ed.) Handbook of discrete and

combinatorial mathematics, pp. 1085–1090,

CRC Press: Boca Raton, 2000.

[16] O. HUDRY and A. LOBSTEIN: Unique (op-

timal) solutions: complexity results for identi-

fying and locating-dominating codes, Theore-

tical Computer Science, Vol. 767, pp. 83–102,

2019.

[17] O. HUDRY and A. LOBSTEIN: Complexity

of unique (optimal) solutions in graphs: Vertex

Cover and Domination, Journal of Combina-

torial Mathematics and Combinatorial Compu-

ting, Vol. 110, pp. 217–240, 2019.

[18] O. HUDRY and A. LOBSTEIN: On the com-

plexity of determining whether there is a unique

Hamiltonian cycle in a graph, WSEAS Trans-

actions on Mathematics, Vol. 21, pp. 433–446,

2022.

[19] D. S. JOHNSON: A catalog of complexity

classes, in: J. van Leeuwen (ed.), Handbook

of theoretical computer science, Vol. A: Algo-

rithms and complexity, Chapter 2, Elsevier:

Amsterdam, 1990.

[20] L. JUBAN: Dichotomy theorem for the

generalized unique satisﬁability problem, in:

G. Ciobanu and G. Paun (eds.) Fundamentals

of computation theory (FCT’99), pp. 327-337,

LNCS 1684: Berlin, 1999.

[21] M. MINOUX: The Unique Horn-Satisﬁability

problem and quadratic Boolean equations, An-

nals of Mathematics and Artiﬁcial Intelligence,

Vol. 6, pp. 253-266, 1992.

[22] C. H. PAPADIMITRIOU: On the complexity of

unique solutions, Journal of the Association for

Computing Machinery, Vol. 31, pp. 392-400,

1984.

[23] C. H. PAPADIMITRIOU: Computational Com-

plexity, Addison-Wesley: Reading, 1994.

[24] C. H. PAPADIMITRIOU and M. YAN-

NAKAKIS: The complexity of facets (and

some facets of complexity), Proceedings of the

14th Annual ACM Symposium on Theory of

Computing, San Francisco, May 1982.

[25] C. H. PAPADIMITRIOU and M. YAN-

NAKAKIS: The complexity of facets (and some

facets of complexity), Journal of Computer and

System Sciences, Vol. 28, pp. 244–259, 1984.

[26] T. J. SCHAEFER: The complexity of satisﬁa-

bility problems, Proceedings of 10th Annual

ACM Symposium on Theory of Computing,

pp. 216–226, 1978.

[27] L. G. VALIANT and V. V. VAZIRANI: NP is as

easy as detecting unique solutions, Theoretical

Computer Science, Vol. 47 (1), pp. 85-93, 1986.

[28] Complexity Zoo, MediaWiki, Available at:

https://complexityzoo.net/Complexity_Zoo

(Accessed June 12, 2023)

WSEAS TRANSACTIONS on MATHEMATICS

DOI: 10.37394/23206.2023.22.54

Olivier Hudry, Antoine Lobstein

E-ISSN: 2224-2880

491

Volume 22, 2023

LNP

co−NP NP

NP−C

DP−C NP −hard −hard = co−NP

co−NP−C

Figure 1: Some classes of complexity.

w2w3w4

to v2

to v2to v2

to v2

aw1

Figure 2: The graph G0of Lemma 3. Because of their particular roles, the vertices v1,v2,w4,a,band dare

represented by black circles.

4,2

4,1

Figure 3: A small example for Theorem 5: c1={x1, x2, x3},c2={x1, x2, x4}. Some vertices or edges are

missing.

WSEAS TRANSACTIONS on MATHEMATICS

DOI: 10.37394/23206.2023.22.54

Olivier Hudry, Antoine Lobstein

E-ISSN: 2224-2880

492

Volume 22, 2023

Contribution of individual authors to

the creation of a scientiﬁc article

(ghostwriting policy)

The two authors contribute equally to all the aspects

of this work.

Sources of funding for research

presented in a scientiﬁc article or

scientiﬁc article itself

None.

Conﬂict of interest

None.

Creative Commons Attribution License 4.0

(Attribution 4.0 International, CC BY 4.0)

This article is published under the terms of the

Creative Commons Attribution License 4.0

https://creativecommons.org/licenses/by/4.0/deed.en

_US

WSEAS TRANSACTIONS on MATHEMATICS

DOI: 10.37394/23206.2023.22.54

Olivier Hudry, Antoine Lobstein

E-ISSN: 2224-2880

493

Volume 22, 2023