Difference between revisions of "Chapter 11"

From The Algorithm Design Manual Solution Wiki
Jump to navigation Jump to search
Line 55: Line 55:
  
  
:[[11.13]]
+
:[[11.13]].In the minimum element set cover problem, we seek a set cover <math>S \subseteq C</math> of a universal set <math>U = {1, . . . , n}</math> such that sum of the sizes of the subsets in <math>S</math> is at most <math>k</math>.
 +
::(a) Show that <math>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.13|Solution]]
  
  
:11.14
+
:11.14. The ''half-Hamiltonian cycle problem'' is, given a graph <math>G</math> with <math>n</math> vertices, determine whether <math>G</math> has a simple cycle of length exactly <math>[n/2]</math>, where the floor function rounds its input down to the nearest integer. Prove that this problem is NP-hard.
  
  
:[[11.15]]
+
:[[11.15]]. The 3-phase power balance problem asks for a way to partition a set of n positive integers into three sets <math>A</math>, <math>B</math>, or <math>C</math> such that <math>\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.15|Solution]]
  
  
:11.16
+
:11.16. Show that the following problem is NP-complete:
 +
:* ''Problem:'' Dense subgraph
 +
:* ''Input:'' A graph <math>G</math>, and integers <math>k</math> and <math>y</math>.
 +
:* ''Output:'' Does <math>G</math> contain a subgraph with exactly <math>k</math> vertices and at least <math>y</math> edges?
  
  
:[[11.17]]
+
:[[11.17]]. Show that the following problem is NP-complete:
 +
:* ''Problem:'' Clique, no-clique
 +
:* ''Input:'' An undirected graph <math>G=(V,E)</math> and an integer <math>k</math>.
 +
:* ''Output:'' Does <math>G</math> contain both a clique of size <math>k</math> and an independent set of size <math>k</math>.
 +
[[11.17|Solution]]
  
  
:11.18
+
: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]]
+
:[[11.19]]. Show that the following problem is NP-hard:
 +
:*''Problem:'' Maximum Common Subgraph
 +
:*''Input:'' Two graphs <math>G_1 = (V_1, E_1)</math> and <math>G_2 = (V_2, E_2)</math>, and a budget <math>b</math>.
 +
:*Output: Two sets of nodes <math>S_1 \subseteq V_1</math> and <math>S_2 \subseteq V_2</math> whose deletion leaves at least <math>b</math> nodes in each graph, and makes the two graphs identical.
 +
[[11.19|Solution]]
  
  
:11.20
+
:11.20. A ''strongly independent'' set is a subset of vertices <math>S</math> in a graph <math>G</math> such that for any two vertices in <math>S</math>, there is no path of length two in <math>G</math>. Prove that strongly independent set is NP-hard.
  
  
:[[11.21]]
+
:[[11.21]]. A ''kite'' is a graph on an even number of vertices, say <math>2n</math>, in which <math>n</math> of the vertices form a clique and the remaining <math>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>2g</math> nodes. Prove that ''max kite'' is NP-hard.
 +
[[11.21|Solution]]
  
 
===Creatvie Reductions===
 
===Creatvie Reductions===

Revision as of 18:55, 11 September 2020

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]

Solution


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.

Solution


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.

Solution


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.

Solution


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?

Solution

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}

  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 [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.)

Solution


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)).

Solution


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].

Solution


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.

Solution


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.

Solution

Creatvie Reductions

11.22


11.23


11.24


11.25


11.26


11.27


11.28


11.29


11.30


Algorithms for Special Cases

11.31


11.32


11.33


11.34


11.35


Back to Chapter List