Latest revision as of 18:43, 11 September 2014

Intractable Problems and Approximation Algorithms

Transformations and Satisfiability

9-1. Give the 3-SAT formula that results from applying the reduction of SAT to 3-SAT for the formula: $ (x+y+\overline z +w+u+\overline v) \cdot (\overline x+\overline y+z+\overline w+u+v) \cdot (x+\overline y+\overline z+w+u+\overline v)\cdot (x+\overline y) $

(Solution 9.1)

9-2. Draw the graph that results from the reduction of 3-SAT to vertex cover for the expression $ (x+ \overline y +z) \cdot (\overline x+y+\overline z) \cdot(\overline x+y+z) \cdot (x+\overline y + \overline x) $

9-3. Suppose we are given a subroutine which can solve the traveling salesman decision problem of page (see book) in, say, linear time. Give an efficient algorithm to find the actual TSP tour by making a polynomial number of calls to this subroutine.

(Solution 9.3)

9-4. Implement a translator that translates satisfiability instances into equivalent 3-SAT instances.

9-5. Design and implement a backtracking algorithm to test whether a set of formulae are satisfiable. What criteria can you use to prune this search?

(Solution 9.5)

9-6. Implement the vertex cover to satisfiability reduction, and run the resulting clauses through a satisfiability testing code. Does this seem like a practical way to compute things?

Basic Reductions

9-7. An instance of the set cover problem consists of a set $ X $ of $ n $ elements, a family $ F $ of subsets of $ X $, and an integer $ k $. The question is, does there exist $ k $ subsets from $ F $ whose union is $ X $? For example, if $ X = \{1,2,3,4\} $ and $ F = \{ \{1,2\}, \{2,3\}, \{4\}, \{2,4\} \} $, there does not exist a solution for $ k=2 $, but there does for $ k=3 $ (for example, $ \{1,2\}, \{2,3\}, \{4\} $). Prove that set cover is NP-complete with a reduction from vertex cover.

(Solution 9.7)

9-8. The baseball card collector problem is as follows. Given packets $ P_1, \ldots, P_m $, each of which contains a subset of this year's baseball cards, is it possible to collect all the year's cards by buying $ \leq k $ packets? For example, if the players are $ \{Aaron, Mays, Ruth, Steven \} $ and the packets are $ \{ \{Aaron,Mays\}, \{Mays,Ruth\}, \{Steven\}, \{Mays,Steven\} \}, $ there does not exist a solution for $ k=2 $, but there does for $ k=3 $, such as $ \{Aaron,Mays\}, \{Mays,Ruth\}, \{Steven\} $ Prove that the baseball card collector problem is NP-hard using a reduction from vertex cover.

9-9. The low-degree spanning tree problem is as follows. Given a graph $ G $ and an integer $ k $, does $ G $ contain a spanning tree such that all vertices in the tree have degree at most $ k $ (obviously, only tree edges count towards the degree)? For example, in the following graph, there is no spanning tree such that all vertices have a degree less than three. \fixedfigsize{pictures/lowdegree.eps}{1.0in}

1. Prove that the low-degree spanning tree problem is NP-hard with a reduction from Hamiltonian path.
2. Now consider the high-degree spanning tree problem, which is as follows. Given a graph $ G $ and an integer $ k $, does $ G $ contain a spanning tree whose highest degree vertex is at least $ k $? In the previous example, there exists a spanning tree with a highest degree of 8. Give an efficient algorithm to solve the high-degree spanning tree problem, and an analysis of its time complexity.

(Solution 9.9)

9-10. Show that the following problem is NP-complete:

• Problem: Dense subgraph
• Input: A graph $ G $, and integers $ k $ and $ y $.
• Output: Does $ G $ contain a subgraph with exactly $ k $ vertices and at least $ y $ edges?

9-11. Show that the following problem is NP-complete:

• Problem: Clique, no-clique
• Input: An undirected graph $ G=(V,E) $ and an integer $ k $.
• Output: Does $ G $ contain both a clique of size $ k $ and an independent set of size $ k $.

(Solution 9.11)

9-12. An Eulerian cycle is a tour that visits every edge in a graph exactly once. An Eulerian subgraph is a subset of the edges and vertices of a graph that has an Eulerian cycle. Prove that the problem of finding the number of edges in the largest Eulerian subgraph of a graph is NP-hard. (Hint: the Hamiltonian circuit problem is NP-hard even if each vertex in the graph is incident upon exactly three edges.)

Creative Reductions

9-13. Prove that the following problem is NP-complete:

• Problem: Hitting Set
• Input: A collection $ C $ of subsets of a set $ S $, positive integer $ k $.
• Output: Does $ S $ contain a subset $ S' $ such that $ |S'| \leq k $ and each subset in $ C $ contains at least one element from $ S' $?

(Solution 9.13)

9-14. Prove that the following problem is NP-complete:

• Problem: Knapsack
• Input: A set $ S $ of $ n $ items, such that the $ i $th item has value $ v_i $ and weight $ w_i $. Two positive integers: weight limit $ W $ and value requirement $ V $.
• Output: Does there exist a subset $ S' \in S $ such that $ \sum_{i \in S'} w_i \leq W $ and $ \sum_{i \in S'} v_i \geq V $?

(Hint: start from integer partition.)

9-15. Prove that the following problem is NP-complete:

• Problem: Hamiltonian Path
• Input: A graph $ G $, and vertices $ s $ and $ t $.
• Output: Does $ G $ contain a path which starts from $ s $, ends at $ t $, and visits all vertices without visiting any vertex more than once?

(Hint: start from Hamiltonian cycle.)

(Solution 9.15)

9-16. Prove that the following problem is NP-complete:

• Problem: Longest Path
• Input: A graph $ G $ and positive integer $ k $.
• Output: Does $ G $ contain a path that visits at least $ k $ different vertices without visiting any vertex more than once?

9-17. Prove that the following problem is NP-complete:

• Problem: Dominating Set
• Input: A graph $ G=(V,E) $ and positive integer $ k $.
• Output: Is there a subset $ V' \in V $ such that $ |V'|\leq k $ where for each vertex $ x \in V $ either $ x \in V' $ or there exists an edge $ (x,y) $, where $ y \in V' $.

(Solution 9.17)

9-18. Prove that the vertex cover problem (does there exist a subset $ S $ of $ k $ vertices in a graph $ G $ such that every edge in $ G $ is incident upon at least one vertex in $ S $?) remains NP-complete even when all the vertices in the graph are restricted to have even degrees.

9-19. Prove that the following problem is NP-complete:

• Problem: Set Packing
• Input: A collection $ C $ of subsets of a set $ S $, positive integer $ k $.
• Output: Does $ S $ contain at least $ k $ disjoint subsets (i.e., such that none of these subsets have any elements in common?)

(Solution 9.19)

9-20. Prove that the following problem is NP-complete:

• Problem: Feedback Vertex Set
• Input: A directed graph $ G=(V,A) $ and positive integer $ k $.
• Output: Is there a subset $ V' \in V $ such that $ |V'|\leq k $, such that deleting the vertices of $ V' $ from $ G $ leaves a DAG?

Algorithms for Special Cases

9-21. A Hamiltonian path $ P $ is a path that visits each vertex exactly once. The problem of testing whether a graph $ G $ contains a Hamiltonian path is NP-complete. There does not have to be an edge in $ G $ from the ending vertex to the starting vertex of $ P $, unlike in the Hamiltonian cycle problem. Give an $ O(n+m) $-time algorithm to test whether a directed acyclic graph $ G $ (a DAG) contains a Hamiltonian path. (Hint: think about topological sorting and DFS.)

(Solution 9.21)

9-22. The $ 2 $-SAT problem is, given a Boolean formula in 2-conjunctive normal form (CNF), to decide whether the formula is satisfiable. $ 2 $-SAT is like $ 3 $-SAT, except that each clause can have only two literals. For example, the following formula is in $ 2 $-CNF: $ (x_1 \vee x_2) \wedge (\bar{x}_2 \vee x_3) \wedge (x_1 \vee \bar{x}_3) $ Give a polynomial-time algorithm to solve $ 2 $-SAT.

P=NP?

9-23. Show that the following problems are in NP:

1. Does graph $ G $ have a simple path (i.e., with no vertex repeated) of length $ k $?
2. Is integer $ n $ composite (i.e., not prime)?
3. Does graph $ G $ have a vertex cover of size $ k $?

(Solution 9.23)

9-24. It was a long open question whether the decision problem Is integer $ n $ a composite number, in other words, not prime? can be computed in time polynomial in the size of its input. Why doesn't the following algorithm suffice to prove it is in P, since it runs in $ O(n) $ time?

  PrimalityTesting($ n $)
     composite := $ false $
     for i := 2 to $ n-1 $ do
        if $ (n\,\bmod\,i) = 0 $ then
           composite := $ true $

Approximation Algorithms

9-25. In the maximum-satisfiability problem, we seek a truth assignment that satisfies as many clauses as possible. Give an heuristic that always satisfies at least half as many clauses as the optimal solution.

(Solution 9.25)

9-26. Consider the following heuristic for vertex cover. Construct a DFS tree of the graph, and delete all the leaves from this tree. What remains must be a vertex cover of the graph. Prove that the size of this cover is at most twice as large as optimal.

9-27. The maximum cut problem for a graph $ G=(V,E) $ seeks to partition the vertices $ V $ into disjoint sets $ A $ and $ B $ so as to maximize the number of edges $ (a,b) \in E $ such that $ a \in A $ and $ b \in B $. Consider the following heuristic for max cut. First assign $ v_1 $ to $ A $ and $ v_2 $ to $ B $. For each remaining vertex, assign it to the side that adds the most edges to the cut. Prove that this cut is at least half as large as the optimal cut.

(Solution 9.27)

9-28. In the bin-packing problem, we are given $ n $ items with weights $ w_1,w_2,...,w_n $, respectively. Our goal is to find the smallest number of bins that will hold the $ n $ objects, where each bin has capacity of at most one kilogram. The first-fit heuristic considers the objects in the order in which they are given. For each object, place it into first bin that has room for it. If no such bin exists, start a new bin. Prove that this heuristic uses at most twice as many bins as the optimal solution.

9-29. For the first-fit heuristic described just above, give an example where the packing it fits uses at least $ 5/3 $ times as many bins as optimal.

(Solution 9.29)

9-30. A vertex coloring of graph $ G=(V,E) $ is an assignment of colors to vertices of $ V $ such that each edge $ (x,y) $ implies that vertices $ x $ and $ y $ are assigned different colors. Give an algorithm for vertex coloring $ G $ using at most $ \Delta+1 $ colors, where $ \Delta $ is the maximum vertex degree of $ G $.