# Chapter 11

Jump to navigation
Jump to search

## Contents

# NP-Completeness

### Transformations and Satisfiability

- 11.1. Give the 3-SAT formula that results from applying the reduction of SAT to 3-SAT for the formula:
- [math]\displaystyle{ (x\or y \or \overline z \or w \or u \or \overline v) \and (\overline x \or \overline y \or z \or \overline w \or u \or v) \and (x \or \overline y \or \overline z \or w \or u \or \overline v)\and (x \or \overline y) }[/math]

- 11.2. Draw the graph that results from the reduction of 3-SAT to vertex cover for the expression
- [math]\displaystyle{ (x \or \overline y \or z) \and (\overline x \or y \or \overline z) \and(\overline x \or y \or z) \and (x \or \overline y \or \overline x) }[/math]

- 11.3. Prove that 4-SAT is NP-hard.

- 11.4.
*Stingy*SAT is the following problem: given a set of clauses (each a disjunction of literals) and an integer [math]\displaystyle{ k }[/math], find a satisfying assignment in which at most [math]\displaystyle{ k }[/math] variables are true, if such an assignment exists. Prove that stingy SAT is NP-hard.

- 11.5. The
*Double SAT*problem asks whether a given satisfiability problem has**at least two different satisfying assignments**. For example, the problem [math]\displaystyle{ {{v1, v2}, {v_1, v_2}, {v_1, v_2}} }[/math] is satisfiable, but has only one solution [math]\displaystyle{ (v_1 =F, v_2 = T) }[/math]. In contrast, [math]\displaystyle{ {{v_1, v_2}, {v_1, v_2}} }[/math] has exactly two solutions. Show that Double-SAT is NP-hard.

- 11.6. Suppose we are given a subroutine that can solve the traveling salesman decision problem on page 357 in (say) linear time. Give an efficient algorithm to find the actual TSP tour by making a polynomial number of calls to this subroutine.

- 11.7. Implement a SAT to 3-SAT reduction that translates satisfiability instances into equivalent 3-SAT instances.

- 11.8. Design and implement a backtracking algorithm to test whether a set of clause sets is satisfiable. What criteria can you use to prune this search?

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

### Basic Reductions

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

- 11.11. The
*baseball card collector problem*is as follows. Given packets [math]\displaystyle{ P_1, \ldots, P_m }[/math], each of which contains a subset of this year's baseball cards, is it possible to collect all the year's cards by buying [math]\displaystyle{ \leq k }[/math] packets? For example, if the players are [math]\displaystyle{ \{Aaron, Mays, Ruth, Steven \} }[/math] and the packets are- [math]\displaystyle{ \{ \{Aaron,Mays\}, \{Mays,Ruth\}, \{Steven\}, \{Mays,Steven\} \}, }[/math]

- there does not exist a solution for [math]\displaystyle{ k=2 }[/math], but there does for [math]\displaystyle{ k=3 }[/math], such as
- [math]\displaystyle{ \{Aaron,Mays\}, \{Mays,Ruth\}, \{Steven\} }[/math]

- Prove that the baseball card collector problem is NP hard using a reduction from vertex cover.

- 11.12. The
*low-degree spanning tree problem*is as follows. Given a graph [math]\displaystyle{ G }[/math] and an integer [math]\displaystyle{ k }[/math], does [math]\displaystyle{ G }[/math] contain a spanning tree such that all vertices in the tree have degree*at most*[math]\displaystyle{ k }[/math] (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.png}{1.0in}

- Prove that the low-degree spanning tree problem is NP-hard with a reduction from Hamiltonian
*path*. - Now consider the
*high-degree spanning tree problem*, which is as follows. Given a graph [math]\displaystyle{ G }[/math] and an integer [math]\displaystyle{ k }[/math], does [math]\displaystyle{ G }[/math] contain a spanning tree whose highest degree vertex is*at least*[math]\displaystyle{ k }[/math]? 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.

- 11.13.In the minimum element set cover problem, we seek a set cover [math]\displaystyle{ S \subseteq C }[/math] of a universal set [math]\displaystyle{ U = {1, . . . , n} }[/math] such that sum of the sizes of the subsets in [math]\displaystyle{ S }[/math] is at most [math]\displaystyle{ k }[/math].
- (a) Show that [math]\displaystyle{ C = {{1, 2, 3}, {1, 3, 4}, {2, 3, 4}, {3, 4, 5}} }[/math] has a cover of size 6, but none of size 5 because of a repeated element.
- (b) Prove that this problem is NP-hard. (Hint: set cover remains hard if all subsets are of the same size.)

- 11.14. The
*half-Hamiltonian cycle problem*is, given a graph [math]\displaystyle{ G }[/math] with [math]\displaystyle{ n }[/math] vertices, determine whether [math]\displaystyle{ G }[/math] has a simple cycle of length exactly [math]\displaystyle{ [n/2] }[/math], where the floor function rounds its input down to the nearest integer. Prove that this problem is NP-hard.

- 11.15. The 3-phase power balance problem asks for a way to partition a set of n positive integers into three sets [math]\displaystyle{ A }[/math], [math]\displaystyle{ B }[/math], or [math]\displaystyle{ C }[/math] such that [math]\displaystyle{ \sum_{i} a_i = \sum_{i} b_i = \sum_{i} c_i }[/math]. Prove that this problem is NP-hard using a reduction from integer partition or subset sum (see Section 10.5 (page 329)).

- 11.16. Show that the following problem is NP-complete:
*Problem:*Dense subgraph*Input:*A graph [math]\displaystyle{ G }[/math], and integers [math]\displaystyle{ k }[/math] and [math]\displaystyle{ y }[/math].*Output:*Does [math]\displaystyle{ G }[/math] contain a subgraph with exactly [math]\displaystyle{ k }[/math] vertices and at least [math]\displaystyle{ y }[/math] edges?

- 11.17. Show that the following problem is NP-complete:
*Problem:*Clique, no-clique*Input:*An undirected graph [math]\displaystyle{ G=(V,E) }[/math] and an integer [math]\displaystyle{ k }[/math].*Output:*Does [math]\displaystyle{ G }[/math] contain both a clique of size [math]\displaystyle{ k }[/math] and an independent set of size [math]\displaystyle{ k }[/math].

- 11.18. n
*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.)

- 11.19. Show that the following problem is NP-hard:
*Problem:*Maximum Common Subgraph*Input:*Two graphs [math]\displaystyle{ G_1 = (V_1, E_1) }[/math] and [math]\displaystyle{ G_2 = (V_2, E_2) }[/math], and a budget [math]\displaystyle{ b }[/math].- Output: Two sets of nodes [math]\displaystyle{ S_1 \subseteq V_1 }[/math] and [math]\displaystyle{ S_2 \subseteq V_2 }[/math] whose deletion leaves at least [math]\displaystyle{ b }[/math] nodes in each graph, and makes the two graphs identical.

- 11.20. A
*strongly independent*set is a subset of vertices [math]\displaystyle{ S }[/math] in a graph [math]\displaystyle{ G }[/math] such that for any two vertices in [math]\displaystyle{ S }[/math], there is no path of length two in [math]\displaystyle{ G }[/math]. Prove that strongly independent set is NP-hard.

- 11.21. A
*kite*is a graph on an even number of vertices, say [math]\displaystyle{ 2n }[/math], in which [math]\displaystyle{ n }[/math] of the vertices form a clique and the remaining [math]\displaystyle{ n }[/math] vertices are connected in a tail that consists of a path joined to one of the vertices of the clique. Given a graph and a goal g, the*max kite*problem asks for a subgraph that is a kite and contains [math]\displaystyle{ 2g }[/math] nodes. Prove that*max kite*is NP-hard.

### Creative Reductions

- 11.22. Prove that the following problem is NP-complete:
*Problem:*Hitting Set*Input:*A collection [math]\displaystyle{ C }[/math] of subsets of a set [math]\displaystyle{ S }[/math], positive integer [math]\displaystyle{ k }[/math].*Output:*Does [math]\displaystyle{ S }[/math] contain a subset [math]\displaystyle{ S' }[/math] such that [math]\displaystyle{ |S'| \leq k }[/math] and each subset in [math]\displaystyle{ C }[/math] contains at least one element from [math]\displaystyle{ S' }[/math]?

- 11.23. Prove that the following problem is NP-complete:
*Problem:*Knapsack*Input:*A set [math]\displaystyle{ S }[/math] of [math]\displaystyle{ n }[/math] items, such that the [math]\displaystyle{ i }[/math]th item has value [math]\displaystyle{ v_i }[/math] and weight [math]\displaystyle{ w_i }[/math]. Two positive integers: weight limit [math]\displaystyle{ W }[/math] and value requirement [math]\displaystyle{ V }[/math].*Output:*Does there exist a subset [math]\displaystyle{ S' \in S }[/math] such that [math]\displaystyle{ \sum_{i \in S'} w_i \leq W }[/math] and [math]\displaystyle{ \sum_{i \in S'} v_i \geq V }[/math]?

- (Hint: start from integer partition.)

- 11.24. Prove that the following problem is NP-complete:
*Problem:*Hamiltonian Path*Input:*A graph [math]\displaystyle{ G }[/math], and vertices [math]\displaystyle{ s }[/math] and [math]\displaystyle{ t }[/math].*Output:*Does [math]\displaystyle{ G }[/math] contain a path which starts from [math]\displaystyle{ s }[/math], ends at [math]\displaystyle{ t }[/math], and visits all vertices without visiting any vertex more than once? (Hint: start from Hamiltonian cycle.)

- 11.25. Prove that the following problem is NP-complete:
*Problem:*Longest Path*Input:*A graph [math]\displaystyle{ G }[/math] and positive integer [math]\displaystyle{ k }[/math].*Output:*Does [math]\displaystyle{ G }[/math] contain a path that visits at least [math]\displaystyle{ k }[/math] different vertices without visiting any vertex more than once?

- 11.26. Prove that the following problem is NP-complete:
*Problem:*Dominating Set*Input:*A graph [math]\displaystyle{ G=(V,E) }[/math] and positive integer [math]\displaystyle{ k }[/math].*Output:*Is there a subset [math]\displaystyle{ V' \in V }[/math] such that [math]\displaystyle{ |V'|\leq k }[/math] where for each vertex [math]\displaystyle{ x \in V }[/math] either [math]\displaystyle{ x \in V' }[/math] or there exists an edge [math]\displaystyle{ (x,y) }[/math], where [math]\displaystyle{ y \in V' }[/math].

- 11.27. Prove that the vertex cover problem (does there exist a subset [math]\displaystyle{ S }[/math] of [math]\displaystyle{ k }[/math] vertices in a graph [math]\displaystyle{ G }[/math] such that every edge in [math]\displaystyle{ G }[/math] is incident upon at least one vertex in [math]\displaystyle{ S }[/math]?) remains NP-complete even when all the vertices in the graph are restricted to have even degrees.

- 11.28. Prove that the following problem is NP-complete:
*Problem:*Set Packing*Input:*A collection [math]\displaystyle{ C }[/math] of subsets of a set [math]\displaystyle{ S }[/math], positive integer [math]\displaystyle{ k }[/math].*Output:*Does [math]\displaystyle{ S }[/math] contain at least [math]\displaystyle{ k }[/math] disjoint subsets (i.e., such that none of these subsets have any elements in common?)

- 11.29. Prove that the following problem is NP-complete:
*Problem:*Feedback Vertex Set*Input:*A directed graph [math]\displaystyle{ G=(V,A) }[/math] and positive integer [math]\displaystyle{ k }[/math].*Output:*Is there a subset [math]\displaystyle{ V' \in V }[/math] such that [math]\displaystyle{ |V'|\leq k }[/math], such that deleting the vertices of [math]\displaystyle{ V' }[/math] from [math]\displaystyle{ G }[/math] leaves a DAG?

- 11.30. Give a reduction from Sudoku to the vertex coloring problem in graphs. Specifically, describe how to take any partially filled Sudoku board and construct a graph that can be colored with nine colors iff the Sudoku board is solvable.

### Algorithms for Special Cases

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

- 11.32. Consider the
*k*-clique problem, which is the general clique problem restricted to graphs in which every vertex has degree at most [math]\displaystyle{ k }[/math]. Prove that*k*-clique has an efficient algorithm for any given [math]\displaystyle{ k }[/math], meaning that [math]\displaystyle{ k }[/math] is a constant.

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

- 11.34, Show that the following problems are in NP:

- Does graph [math]\displaystyle{ G }[/math] have a simple path (i.e., with no vertex repeated) of length [math]\displaystyle{ k }[/math]? \#Is integer [math]\displaystyle{ n }[/math] composite (i.e., not prime)?
- Does graph [math]\displaystyle{ G }[/math] have a vertex cover of size [math]\displaystyle{ k }[/math]?

- 11.35. Until 2002, it was an open question whether the decision problem
*Is integer [math]\displaystyle{ n }[/math] 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 [math]\displaystyle{ O(n) }[/math] time?

PrimalityTesting([math]\displaystyle{ n }[/math]) composite := [math]\displaystyle{ false }[/math] for i := 2 to [math]\displaystyle{ n-1 }[/math] do if [math]\displaystyle{ (n\,\bmod\,i) = 0 }[/math] then composite := [math]\displaystyle{ true }[/math]

Back to Chapter List