6.046 Problem Set 10

Chris Laas: Section G

May 5, 2000

Problem 10-1

(a) It’s quite easy to see that, if there exists a spanning graph of degree d for a graph G = (V, E) and a vertex u with degree greater than d, then there must exist some edge (u, v) such that the graph with that edge removed still has a spanning graph of degree d. For, if there existed no such edge, then every spanning graph of degree d would contain all of the edges incident upon u, which would mean that the degree of u in the spanning graph would still be greater that d, which is a contradiction.

Thus, we need only to remove such edges until a graph of degree d remains. A very simple, inefficient but polynomial-time, algorithm to do this would be:

1  Search-SG(< G, d >)
2  \underline{if} there exists a vertex u ∈ V [G] such that degree(u) > d
3  \underline{then} \underline{for} each vertex v ∈ V [G] such that (u, v) ∈ E[G]
4  G′ ← (V [G], E[G] − {(u, v)})
5  \underline{if} Decision-SG(< G′, d >)
6  \underline{then} \underline{return} Search-SG(< G′, d >)
7  \underline{else} \underline{return} G

Correctness follows from the correctness of the above proof, since this algorithm is a direct translation from the wording of the theorem into pseudocode. Termination is guaranteed, since one edge is removed on every recursive call, and the algorithm terminates as soon as the degree of the graph is d or less.

Even using the most inefficient search algorithms (linear in number of vertices), this algorithm calls Decision-SG at most O(V E) times, and takes at most O(V E) overhead, since one edge is removed on every recursive call. Thus, if Decision-SG runs in polynomial time, then Search-SG runs in polynomial time.

(b) Your co-worker, by designing an algorithm for solving the NP-complete problem 3-SAT in polynomial time, has just proven that P = NP, and is probably either rich and famous, or dead, by now. Regardless, since P = NP, all problems in NP can be solved by a polynomial-time algorithm. Hence, we need only prove that the spanning-graph-of-degree-d problem is in NP.

Let the certificate be the set of vertices and edges which make up a spanning graph of degree d for the graph. Then it is trivial to check in polynomial time that all of the vertices of the original graph are in the spanning graph and that all of the vertices have degree less than or equal to d in the spanning graph; and a linear-time breadth-first search can be used to verify that the spanning graph is connected, which proves that it spans the original graph.

Thus, spanning-graph-of-degree-d is in NP; since 3-SAT is NP-complete and 3-SAT is in P, we have that spanning-graph-of-degree-d is in P. Thus, there exists a polynomial-time algorithm that solves the spanning-graph-of-degree-d problem.

We can use this as a subroutine to solves the smallest degree spanning graph, simply by checking whether there exists a spanning graph of degree d for all d between 1 and ∥V ∥, inclusive. This would call spanning-graph-of-degree-d at most ∥V ∥ times, and thus would be polynomial-time.

Problem 10-2

(a) We need to show that, if we could solve the knapsack problem in polynomial time, then we could solve the subset-sum problem in polynomial time.

Let’s say we have an instance of the subset-sum problem: a set S = {s_{1}, s_{2}, …, s_{n}} of integers and a target integer t. We can construct an instance of the knapsack problem by setting the object sizes to be the integers s_{i}, setting the worths to be w_{i} = s_{i}, and setting the knapsack size B = t. If we can solve the knapsack problem in polynomial time, then we can get the maximum total worth of a subset of the objects in polynomial time. If this worth is less than t, then there clearly exists no subset of the s_{i} which adds up to t; if the total worth is equal to t, then there does exist a subset which adds up to t. The total worth cannot be greater than t, since the subset’s size would have to be greater than t and thus would not fit in the knapsack.

Thus, since the subset-sum problem is NP-complete, the knapsack problem is NP-hard.

(b) Let’s say that we have a knapsack of size B. Let there be two objects in our input set: one with size B and value v, for some value v > 1 that we choose, and another with size B/2v and value 1. Since \frac{v}{B} < \frac{1}{B/2v}, the greedy algorithm chooses the object with size B/2v first, and the other object doesn’t fit; thus, the greedy algorithm gives a total value of 1. On the other hand, the optimal solution would be to choose the object with size B and value v, which gives a total value v > 1. Since v can be made arbitrarily large, the greedy algorithm could be made to give an arbitrarily small fraction of the optimal total worth.

(c) Consider the fractional solution: at the time the greedy algorithm first rejects an object which could fit in the empty knapsack, instead split the object and put the amount that fits into the rest of the backpack. It is not possible for any non-fractional solution to have higher utility than this solution, because the fractional solution has the greatest possible value per unit size for every unit of size. Thus, the optimal solution for the non-fractional case cannot have greater value than the fractional solution.

Now, let us assume, for purposes of contradiction, that our new improved algorithm is not a 2-approximation algorithm. Then, both the total value of the greedy solution v_{g} and the value of the single most valuable object that fits in the knapsack v_{1} are less than one-half of the optimal value v_{o}, since if either were greater than one-half, the maximum of the two would have to be greater than one-half. Thus, since the optimal value is less than the value of the fractional solution v_{f}, we know that both v_{g} and v_{1} are less than \frac{v_{f}}{2} .

Since the fractional solution is achieved by taking the greedy solution and adding a fraction ϕ (0 < ϕ < 1) of the next object which could fit in the empty knapsack, it is the case that v_{f} = v_{g}+ϕv_{n}, where v_{n} is the value of this next object. Since v_{g} < \frac{v_{f}}{2} , we must have ϕv_{n} > \frac{v_{f}}{2} , and since ϕ < 1, v_{n} > \frac{v_{f}}{2} . But then this single object has value greater than half the value of the fractional solution, which contradicts the assumption that the value of the single most valuable object that fits in your knapsack is less than half the value of the fractional solution.

Thus, the assumption is wrong, and we have proven that this algorithm is a 2-approximation algorithm.

Problem 10-3

(a) This is an open question: it depends on whether P = NP.

If P = NP, then it is true: for any L_{1}, L_{2} ∈ NP, both L_{1} and L_{2} are in P.

If P ≠ NP, then it is false: there exists some L_{2} which is in NP but not in P. Then, for every L_{1} ∈ P, we have that L_{1} <_{p} L_{2}, but L_{2} ∉ P. This is because any language in P is polynomial-time reducible to any other language, trivially.

(b) True: this is a fundamental lemma of reducibility. In fact, it is lemma 36.3 on CLR page 931.

(c) True: this is a rephrasing of the standard method of proving NPcompleteness, i.e. “If L_{1} is NP-complete, and L_{1} <_{p} L_{2}, and L_{2} ∈ NP, then L_{2} is NP-complete.” It is lemma 36.8 on CLR page 939.

(d) False: L_{1} and L_{2} might both be outside of NP, but reducible in polynomial time to each other. For example, if we choose L_{1} to be some language outside of NP, we could choose L_{2} to be equal to L_{1}; this would trivially satisfy the conditions L_{1} <_{p} L_{2} and L_{2} <_{p} L_{1}, but clearly the languages could not be NP-complete, since they are not in NP.

(e) True: if L_{1} and L_{2} are both NP-complete, then clearly L_{2} is in NP; and thus, by the definition of NP-completeness, L_{2} <_{p} L_{1}, since L_{1} is NP-complete.

Problem 10-4

(a) First, we must show that the directed Hamiltonian path problem is in NP. Given a graph G = (V, E), let the certificate be the sequence of ∥V ∥ vertices that make up the path. The verification algorithm checks that this sequence contains each vertex in V exactly once and that it forms a path in G from u to v; this can be done in polynomial time.

We now must prove that if we could solve the directed Hamiltonian path problem in polynomial time, then we could solve the Hamiltonian cycle problem in polynomial time.

Let us consider an instance of the Hamiltonian cycle problem: an undirected graph G = (V, E). For every edge (u, v) ∈ E, construct a directed graph G′ = (V, E′), where (x, y) ∈ E′ and (y, x) ∈ E′ if and only if (x, y) ∈ E and (x, y) ≠ (u, v). Hence, G′ is a directed-graph version of the graph G with the edge (u, v) removed (both forward and back edges in the directed graph). This can clearly be constructed in polynomial time; and, it can be used as a problem instance of the directed Hamiltonian path problem with u and v as the endpoints.

If there exists a directed Hamiltonian path in G′ for some endpoints (u, v) as specified above, then it is clear that there exists a Hamiltonian cycle in the original graph G: simply take the sequence of nodes returned by the path problem, and add the edge (u, v) to create a cycle in the undirected graph. Conversely, if there exists a Hamiltonian cycle in the graph G, then removing any edge (u, v) from the cycle leaves a Hamiltonian path from u to v in the directed graph G′. Thus, there exists a directed Hamiltonian path in G′ for some endpoints u and v such that (u, v) is an edge in G, if and only if there exists a Hamiltonian cycle in G.

Thus, we have provided a polynomial-time reduction from Hamiltoniancycle to directed-Hamiltonian-path.

(b) If the graph is a DAG, then it is simple to solve the directed Hamiltonian path problem. Perform a topological sort on the graph: this can be done in linear time. Then there exists a directed Hamiltonian path from u to v in the graph if and only if u is the first element in the list, v is the last, and there is an edge between any two adjacent vertices in the list. For, assume that that is the case: then the Hamiltonian path from u to v consists of the list produced by the topological sort. On the other hand, if there exists no edge between two adjacent vertices x and y (with x coming before y), then no path in the graph can contain both x and y, since any path that contains x must, if it continues, go on to a vertex after y, and there are no back edges in the topologically sorted list. (And, if u is not the first vertex, the first vertex cannot be reached from any path starting at u; and if v is not the last vertex, then the last vertex cannot be touched by any path that ends at v.)

To spell the algorithm out in pseudocode (although it’s been described sufficiently):

1  DAG-Directed-Hamiltonian-Path(G, u, v)
2  V ← Topological-Sort(G)
3  \underline{if} u ≠ First[V] or v ≠ Last[V]
4  \underline{then} \underline{return} false
5  \underline{for} i ← 1 . . ∥V ∥ − 1
6  \underline{if} (V [i], V [i + 1]) ∉ E[G]
7  \underline{then} \underline{return} false
8  \underline{return} true

Correctness is guaranteed by the above if-and-only-if relation; termination is guaranteed by the explicit bounds on the loop. The run time is linear in the size of the input graph, since Topological-Sort runs in linear time, and the loop has at most ∥V ∥ iterations.

Problem 10-5

(a) True. If the runtimes of all subroutines are bounded above by f(n) = O(n^{k}) and the output sizes are bounded by g(n) = O(n^{l}), and the algorithm A makes a constant number of calls c to subroutines, then the run time of the algorithm A is bounded by cf(n) = O(n^{k}) (and the output size is bounded by cg(n) = O(n^{l})). Thus A runs in polynomial time.

(b) True. If the runtimes of all decision-procedure subroutines are bounded above by f(n) = O(n^{k}), and the algorithm A makes a polynomial number of calls F (n) = O(n^{K}) to subroutines, then the run time of the algorithm A is bounded by F (n)f(n) = O(n^{k+K}) (and the output size is bounded by F (n) = O(n^{K})). Thus A runs in polynomial time.

(c) True. If the runtimes of all decision-procedure subroutines are bounded above by f(n) = O(n^{k}) and the output sizes are bounded by g(n) = O(n^{l}), and the algorithm A makes a polynomial number of calls F (n) = O(n^{K}) to subroutines, then the run time of the algorithm A is bounded by F (n)f(n) = O(n^{k+K}) (and the output size is bounded by F (n)g(n) = O(n^{l+K}). Thus A runs in polynomial time.