Hw8 solutions PDF

Preview

Summary

Homework 8-SOLUTIONS...

Description

15-351 / 15-650 / 02-613 Homework #8: NP-completeness Due: April 28 by 9:00am You may talk with your classmates about these problems, but you must write up your solutions independently, without using common notes or worksheets. You must indicate at the top of your homework with whom you worked. Your write up should be clear and concise. It should be submitted via GradeScope as a typeset PDF. For the following problems, you can assume that Independent Set, 3-SAT, Graph Coloring, and Hamiltonian Path (and its variants) are NP-complete. 1. The Clique problem is the following: given an undirected graph G = (V, E) and a positive integer k ≤ |V |, does G contain a set C of ≥ k vertices such that every two vertices u, v ∈ C are connected by an edge? Prove Clique is NP-complete. Clique is in NP: a certificate is a list of nodes C . It takes a polynomial time in the size of the graph G to check that |C| ≥ k and that every pair of nodes in C has an edge. We do a reduction from Independent Set. Let (G, k) be an instance of the Independent Set, where G is a graph and k is an integer. We create G′ the complement graph of G. G′ has the same node set than G and (u, v) is an edge of G′ iff (u, v ) is not an edge of G. The construction of G′ is done in polynomial time. It is easy to check that a set of nodes C is an independent set in G iff C is a clique in G′ . 2. Suppose G = (V, E) is an undirected graph. A strongly independent set is a subset S of vertices such that for any two vertices u, v ∈ S there is no path of length ≤ 2 between u and v. Consider the following Strongly Independent Set (SIS) problem: Given an undirected graph G = (V, E) and an integer k, does G have a strongly independent set of size k ? Prove SIS is NP-complete. SIS is in NP: a certificate is a set of nodes S. To check that it is a strongly independent set we do a BFS traversal of depth at most two starting from each node of S, to check that there is no path of length ≤ 2. This is a polynomial time work in the size of the input graph. We do a reduction from Independent Set. Given an instance (G, k), where G is a graph and k is an integer, we create a graph which has the same nodes than G plus an extra node ue for each edge e of G. For every edge e = (u, v) of G we create the edges (u, ue ) and (ue , v) in G′ . Additionally, if two edges e and f in G share an endpoint, we create the edge (ue , uf ) in G′ . See the picture below. Given an independent set S of size k in G, S is also a subset of the nodes of G′ . A path of length 2 or more between nodes of S in G becomes a path of length 3 or more in G′ . Hence S is a strongly independent set of length k in G′ . Conversely, let S ′ be a strongly independent set of size k in G′ . Let S be the set constructed ′ , then x represent an edge (u, v ) as follows: if x ∈ S ′ ∩ VG , then we put x in S. If x ∈ S ′ ∩ E G in G and we put u in S, but not v (choose one of the endpoint). Hence S ′ has the same size as S . Looking at the picture, if u ∈ S ′ , then u ∈ S and none of ue , v, ue′ are in S ′ . The closest node of G′ that can be in S ′ is either w or ue′′ , which are at distance 3. Hence the closest node to u in S is w, because w ∈ S ′ or because w was the chosen endpoint of ue′′ to be in S. Therefore no node adjacent to u is in S . 1

Similarly, if ue ∈ S ′ , then the closest node of G′ that can be in S ′ is either x or ue′′′ at distance 3. Hence the closest chosen nodes in S are v (as the chosen endpoint of ue ) and x (because x ∈ S ′ or x is the chosen endpoint of ue′′′ ). v and x are not adjacent in G. The set S constructed is an independent set of G constructed from a strongly independent set of G′ and of the same size.

3. The Longest Path problem: given an undirected graph G = (V, E), and a positive integer K ≤ |V |, does G contain a simple path (a path visiting no vertex more than once) with K or more edges? Prove that Longest Path is NP-complete. Longest Path is in NP: a certificate is an ordered list L of nodes. It takes a polynomial time in the size of the input graph G to check that |L| ≥ K , that every pair of consecutive nodes in L has an edge in G and that the same node does not occur twice in L. We do a reduction from Hamiltonian Path. Let G be an instance of the Hamiltonian Path problem, where G is a graph. We create an instance of the Longest Path problem (G, |VG | − 1), that is we ask whether graph G has a path containing all the nodes. A solution to the Hamiltonian Path problem is a path of length |VG | − 1. Conversely, a path of length |VG | − 1 is a Hamiltonian path. 4. Let Integer Linear Programming be the decision problem asking whether a given maximization integer linear program has a solution of objective value ≥ a given k. Prove Integer Linear Programming is NP-complete. There are many possible solutions to this question, as many NP-complete problems can be naturally expressed as an Integer Linear Program. First example, from Vertex Cover. Given an instance (G, k) of Vertex Cover, where G is a graph and k is an integer, we create the following Integer Linear Program decision problem. We have a binary variable xu for every node u ∈ VG . The constraints are xu +xv ≥ 1 for every edge e = (u, v) ∈ EG . It means that every Pedge must be covered by at least one of its end point. The decision question is whether u∈G xu ≤ k. It is easy to check that solutions from Vertex Cover give a solution to Integer Linear Programming, and that the converse is true as well. Second example, from 3SAT. Given a set of k clauses, Ci , 1 ≤ i ≤ k, we create the following Integer Linear Program decision problem. For each boolean variable xi , 1 ≤ i ≤ n in the boolean expression, we have a corresponding variable yi ∈ {0, 1} in the Integer Linear Program. For each clause Ci we have a variable ci . Here is an example of a constraint: given a clause C1 = (x1 ∨ x¯2 ∨ x3 ), we create the constraint c1 ≤ y1 + (1 − y2 ) + y3 . That is, the variable c1 P can be set to 1 only if at least 1 term in the clause is true. The decision question is whether 1≤i≤k ci ≥ k. It is easy to check that a solution to the 3SAT instance gives a solution to the Integer Linear Programming instance, and the converse is also true.

2...