University of Sussex Spring 2021 Informatics
Limits of Computation
Exercises 9
Polynomial-time Reduction and NP-completeness
(Lectures 19–20)
1. Show that the polynomial time reduction relation is transitive. In otherwords,showthatifA≤P BandB≤P CthenA≤P C. Hint: You need to unfold the definition of ≤P in the assumptions, then compose the result in the right way so that you get the desired conditions that can be “folded back” to get A ≤P C.
2. A k-clique in an undirected graph G = (V, E) is a set of k vertices (nodes) S ⊆ V such that G has an edge between every pair of nodes in this set S, or in other words, for all v,w ∈ S with v ̸= w we have that (v,w) ∈ E.
(a) Draw a graph with a 3-clique.
(b) The Clique-Problem is defined as follows:
CLIQUE = {(G, k) | undirected graph G has a k-clique }. So a CLIQUE instance is an undirected graph and a positive natural number k and the problem question is whether G has a k-clique.
Show that CLIQUE is in NP.
(c) Next, we want to show that CLIQUE is also NP-hard with the help of a polynomial time reduction SAT ≤P CLIQUE. We define the reduction function as follows: Given a boolean formula in conjunctive normal form F = C1 ∧C2 ∧. . .∧Cn, let f(F) = (GF,n) where GF = (V,E) is an undirected graph such that
• V is the set of occurrences of literals in F
• E = {(v,w) |v and w are not in the same clause of F
and neither is the negation of the other }
1
For instance for the expression
F =(A∨¬B)∧(B∨C)∧(¬A∨C)
we get f(F) = ((V,E),3) with V = {A,¬B,B,C1,¬A,C2}. Note that we have two occurrences of C which we need to distinguish. According to the above the set of edges must be as follows:
E = { (A, B), (A, C1), (A, C2), (¬B, C2), (¬B, ¬A), (C1, ¬B), (C2, B), (¬A, C1), (¬A, B), (C2, C1)}.
i. Draw the graph f(F) from above.
ii. Find 3-cliques in the graph. How many can you find?
iii. For each 3-clique identified above, explain how it deter- mines a truth assignment (valuation) θ of F such that θ(F) = true for this particular example.
iv. Argue that the reduction function is computable in poly- nomial time.
2