3. The class NP: Reducibility and completeness 35

Clique. For a graph G and an integer k determine whether the graph

has a k-clique (a set of k vertices such that every two of its elements are

connected by an edge).

Problems

[3] 3.1. Prove that one can check the satisfiability of a 2-CNF (a conjunc-

tion of disjunctions, each containing two literals) in polynomial time.

[2] 3.2. Prove that the problem of the existence of an Euler cycle in an

undirected graph (an Euler cycle is a cycle that traverses each edge exactly

once) belongs to P.

[1!] 3.3. Suppose we have an NP-oracle — a magic device that can imme-

diately solve any instance of the SAT problem for us. In other words, for

any propositional formula the oracle tells whether it is satisfiable or not.

Prove that there is a polynomial-time algorithm that finds a satisfying as-

signment to a given formula by making a polynomial number of queries to

the oracle. (A similar statement is true for the Hamiltonian cycle: finding a

Hamiltonian cycle in a graph is at most polynomially harder than checking

for its existence.)

[3!] 3.4. There are n boys and n girls. It is known which boys agree to

dance with which girls and vice versa. We want to know whether there

exists a perfect matching (the boys and the girls can dance in pairs so that

everybody is satisfied). Prove that this problem belongs not only to NP

(which is almost evident), but also to P.

3.5. Construct

[2!] (a) a polynomial reduction of the 3-SAT problem to the clique problem;

[3] (b) a polynomial reduction of 3-SAT to Clique that conserves the num-

ber of solutions (if a 3-CNF F is transformed into a graph H and an integer

k, then the number of satisfying assignments for F equals the number of

k-cliques in H).

3.6. Construct

[2!] (a) a polynomial reduction of 3-SAT to 3-coloring;

[3] (b) the same as for (a), with the additional requirement that the number

of satisfying assignments is one sixth of the number of 3-colorings of the

corresponding graph.

[2] 3.7. A tile is a (1 × 1)-square whose sides are marked with letters. We

want to cover an (n × n)-square with

n2

tiles; it is known which letters

are allowed at the boundary of the n × n-square and which letters can be

adjacent.