|
|
| Line 1: |
Line 1: |
| − | =NP-Completeness= | + | Init: |
| | + | k=0 |
| | | | |
| − | ===Transformations and Satisfiability=== | + | Insert X: |
| | + | k = k+1; |
| | + | A[X] = k; |
| | + | B[k] = X; |
| | | | |
| − | :[[11.1]]. Give the 3-SAT formula that results from applying the reduction of SAT to 3-SAT for the formula: | + | Search X: |
| − | :::<math> (x\or y \or \overline z \or w \or u \or \overline v) \and (\overline x \or \overline
| + | return (A[X] < k) and (B[A[X]] == X) |
| − | 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.1|Solution]] | |
| | | | |
| | + | Delete X: |
| | + | A[B[k]] = A[X]; |
| | + | B[A[X]] = B[k]; |
| | + | k = k-1; |
| | | | |
| − | :11.2. Draw the graph that results from the reduction of 3-SAT to vertex cover for the expression
| + | Please note that this data structure doesn't support inserting the same X more than once. |
| − | :::<math>(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.
| + | Back to [[Chapter 3]] |
| − | [[11.3|Solution]]
| |
| − | | |
| − | | |
| − | :11.4. ''Stingy'' SAT is the following problem: given a set of clauses (each a disjunction of literals) and an integer <math>k</math>, find a satisfying assignment in which at most <math>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>{{v1, v2}, {v_1, v_2}, {v_1, v_2}}</math> is satisfiable, but has only one solution <math>(v_1 =F, v_2 = T)</math>. In contrast, <math>{{v_1, v_2}, {v_1, v_2}}</math> has exactly two solutions. Show that Double-SAT is NP-hard.
| |
| − | [[11.5|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.
| |
| − | [[11.7|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?
| |
| − | [[11.9|Solution]]
| |
| − | | |
| − | ===Basic Reductions===
| |
| − | | |
| − | :11.10. An instance of the ''set cover'' problem consists of a set <math>X</math> of <math>n</math> elements, a family <math>F</math> of subsets of <math>X</math>, and an integer <math>k</math>. The question is, does there exist <math>k</math> subsets from <math>F</math> whose union is <math>X</math>? For example, if <math>X = \{1,2,3,4\}</math> and <math>F = \{ \{1,2\}, \{2,3\}, \{4\}, \{2,4\} \}</math>, there does not exist a solution for <math>k=2</math>, but there does for <math>k=3</math> (for example, <math> \{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>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>\leq k</math> packets? For example, if the players are <math> \{Aaron, Mays, Ruth, Steven \} </math> and the packets are
| |
| − | :::<math> \{ \{Aaron,Mays\}, \{Mays,Ruth\}, \{Steven\}, \{Mays,Steven\} \}, </math>
| |
| − | :there does not exist a solution for <math>k=2</math>, but there does for <math>k=3</math>, such as
| |
| − | :::<math> \{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>G</math> and an integer <math>k</math>, does <math>G</math> contain a spanning tree such that all vertices in the tree have degree ''at most'' <math>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>G</math> and an integer <math>k</math>, does <math>G</math> contain a spanning tree whose highest degree vertex is ''at least'' <math>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>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. 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]]. 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. 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]]. 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. 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>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. 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]]. 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]]
| |
| − | | |
| − | ===Creative Reductions===
| |
| − | | |
| − | :11.22. Prove that the following problem is NP-complete:
| |
| − | :* ''Problem:'' Hitting Set
| |
| − | :* ''Input:'' A collection <math>C</math> of subsets of a set <math>S</math>, positive integer <math>k</math>.
| |
| − | :* ''Output:'' Does <math>S</math> contain a subset <math>S'</math> such that <math>|S'| \leq k</math> and each subset in <math>C</math> contains at least one element from <math>S'</math>?
| |
| − | | |
| − | | |
| − | :[[11.23]]. Prove that the following problem is NP-complete:
| |
| − | :* ''Problem:'' Knapsack
| |
| − | :* ''Input:'' A set <math>S</math> of <math>n</math> items, such that the <math>i</math>th item has value <math>v_i</math> and weight <math>w_i</math>. Two positive integers: weight limit <math>W</math> and value requirement <math>V</math>.
| |
| − | :* ''Output:'' Does there exist a subset <math>S' \in S</math> such that <math>\sum_{i \in S'} w_i \leq W</math> and <math>\sum_{i \in S'} v_i \geq V</math>?
| |
| − | :(Hint: start from integer partition.)
| |
| − | [[11.23|Solution]]
| |
| − | | |
| − | | |
| − | :11.24. Prove that the following problem is NP-complete:
| |
| − | :* ''Problem:'' Hamiltonian Path
| |
| − | :* ''Input:'' A graph <math>G</math>, and vertices <math>s</math> and <math>t</math>.
| |
| − | :* ''Output:'' Does <math>G</math> contain a path which starts from <math>s</math>, ends at <math>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>G</math> and positive integer <math>k</math>.
| |
| − | :* ''Output:'' Does <math>G</math> contain a path that visits at least <math>k</math> different vertices without visiting any vertex more than once?
| |
| − | [[11.25|Solution]]
| |
| − | | |
| − | | |
| − | :11.26. Prove that the following problem is NP-complete:
| |
| − | :* ''Problem:'' Dominating Set
| |
| − | :* ''Input:'' A graph <math>G=(V,E)</math> and positive integer <math>k</math>.
| |
| − | :* ''Output:'' Is there a subset <math>V' \in V</math> such that <math>|V'|\leq k</math> where for each vertex <math>x \in V</math> either <math>x \in V'</math> or there exists an edge <math>(x,y)</math>, where <math>y \in V'</math>.
| |
| − | | |
| − | | |
| − | :[[11.27]]. Prove that the vertex cover problem (does there exist a subset <math>S</math> of <math>k</math> vertices in a graph <math>G</math> such that every edge in <math>G</math> is incident upon at least one vertex in <math>S</math>?) remains NP-complete even when all the vertices in the graph are restricted to have even degrees.
| |
| − | [[11.27|Solution]]
| |
| − | | |
| − | | |
| − | :11.28. Prove that the following problem is NP-complete:
| |
| − | :* ''Problem:'' Set Packing
| |
| − | :* ''Input:'' A collection <math>C</math> of subsets of a set <math>S</math>, positive integer <math>k</math>.
| |
| − | :* ''Output:'' Does <math>S</math> contain at least <math>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>G=(V,A)</math> and positive integer <math>k</math>.
| |
| − | :* ''Output:'' Is there a subset <math>V' \in V</math> such that <math>|V'|\leq k</math>, such that deleting the vertices of <math>V'</math> from <math>G</math> leaves a DAG?
| |
| − | [[11.29|Solution]]
| |
| − | | |
| − | | |
| − | :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]]
| |
| − | | |
| − | | |
| − | :11.32
| |
| − | | |
| − | | |
| − | :[[11.33]]
| |
| − | | |
| − | | |
| − | :11.34
| |
| − | | |
| − | | |
| − | :[[11.35]]
| |
| − | | |
| − | | |
| − | Back to [[Chapter List]] | |
