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).
[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
tiles; it is known which letters
are allowed at the boundary of the n × n-square and which letters can be
Previous Page Next Page