Chapter 7

Exercises on NP-completenes s

This chapter presents a set of exercises related to NP-completeness. The aim

of most questions is to prove the NP-completeness of a new problem, so that

the reader will become more familiar with this reasoning.

We assume in the ﬁrst sections that 2-PARTITION is NP-complete, as

stated in Section 6.4.5, so that we can warm up with easy reductions in Sec-

tion 7.1. We also provide thematic exercises around graph coloring (Sec-

tion 7.2) and scheduling (Section 7.3). More involved reductions are proposed

in Section 7.4. Finally, the NP-completeness of 2-PARTITION is proved in

Section 7.5.

Some of the exercises contain hints. Additional hints can be found on

page 155 at the beginning of Section 7.6, which is the section where solutions

to all of the exercises are given.

7.1 Easy reductions

Exercise 7.1: Wheel (solution p. 156)

Prove that the following decision problem is NP-complete. Given a graph

G = (V, E) and an integer K 3, does G include a wheel of size K, i.e., a

set of K + 1 vertices w, v

1

, v

2

, . . . , v

K

such that E contains the set of edges

(v

K

, v

1

), {(v

i

, v

i+1

)}

1i<K

, and {(v

i

, w)}

1iK

(w is the center of the wheel)?

Exercise 7.2: Knights of the round tab le (solution p. 156)

Prove that the following decision pr oblem is NP-complete. Given n knights,

and a set of pairs of knights who are enemies, is it possible to arrange the

knights around a round table so that two enemies do not sit side by side?

Exercise 7.3: Variants of CLIQUE (solution p. 157)

Prove that the two following variants of CLIQUE are also NP-complete prob-

lems.

149

© 2014 by Taylor & Francis Group, LLC

150 Chapter 7. Exercises on NP-completeness

1. TWO-CLIQUES: Let G = (V, E) be a graph and k be an integer such

that 1 k |V |. Do there exist two disjoint cliqu es of size k in G (i.e.,

two disjoint complete subgraphs of G with k vertices)?

2. CLIQUE-REG-GRAPH: Let G = (V, E) be a graph whose vertices are

all of the same degree and k be an integer. Does there exist a clique of

size k in G?

Exercise 7.4: Path with vertex pairs (solution p. 158)

Prove that the following decision p robl em is NP-complete. Let G = (V, E) be

a directed graph (therefore, in this graph, the arc (u, v) is diﬀerent from the

arc (v, u)). Let s and t be two vertices of G and let P = {(a

1

, b

1

), . . . , (a

n

, b

n

)}

be a list of pairs of vertices of G. Does there exist a directed path from s to t

in G that includes at most one vertex from each of the pairs in the list P ?

(Hint: Build a reduction from 3-SAT.)

Exercise 7.5: VERTEX-COVER with even degr ees (solution

p. 158)

Prove that the following decision p robl em is NP-complete. Let G = (V, E) be

a graph whose vertices all have an even degree, and let k be a positive integer.

Is there a subset of the vertices of G that covers all the edges of G and whose

size is at most k?

Exercise 7.6: Around 2-PARTITION (solution p. 159)

Reminder: All integers in the 2-PARTITION problem and its variants must

be (strictly) positive. Furthermore, we assume that 2-PARTITION is NP-

complete.

Prove that the four following decision problems are NP-complete:

1. 2PARTNEVEN: Given 2n integers a

1

, a

2

, . . . , a

2n

, is there a subset I of

{1, . . . , 2n} such that

i∈I

a

i

=

i /∈I

a

i

?

2. 2PARTEQ: Given 2n integers a

1

, a

2

, . . . , a

2n

, is there a subset I of

{1, . . . , 2n} such that

i∈I

a

i

=

i /∈I

a

i

, with |I| = n?

3. 2PARTODDEVEN: Given 2n integers a

1

, a

2

, . . . , a

2n

, is there a subset I

of {1, . . . , 2n} such that

i∈I

a

i

=

i /∈I

a

i

with, for any j ∈ {1, . . . , n},

exactly one integer between a

2j−1

and a

2j

belongs to I?

4. PARTITIONIN3: Given n integers a

1

, a

2

, . . . , a

n

, are there three disjoint

subsets I

1

, I

2

, and I

3

of {1, . . . , n} such that

i∈I

1

a

i

=

i∈I

2

a

i

=

i∈I

3

a

i

?

5. Are the above decision problems NP-complete in the strong sense or the

weak sense?

© 2014 by Taylor & Francis Group, LLC

Start Free Trial

No credit card required