O'Reilly logo

A Guide to Algorithm Design by Frédéric Vivien, Yves Robert, Anne Benoit

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

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 first 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 different 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
iI
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
iI
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
iI
a
i
=
i /I
a
i
with, for any j {1, . . . , n},
exactly one integer between a
2j1
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
iI
1
a
i
=
iI
2
a
i
=
iI
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

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required