Difference between revisions of "Hardness-TADM2E"
(Recovering wiki) |
(Recovering wiki) |
||
Line 5: | Line 5: | ||
'''Transformations and Satisfiability''' | '''Transformations and Satisfiability''' | ||
− | + | <br>9-1. | |
Give the 3-SAT formula that results from applying the reduction of SAT to 3-SAT | Give the 3-SAT formula that results from applying the reduction of SAT to 3-SAT | ||
for the formula: | for the formula: | ||
− | + | <math> (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) </math> | |
[[TADM2E 9.1|(Solution 9.1)]] | [[TADM2E 9.1|(Solution 9.1)]] | ||
− | + | <br>9-2. | |
Draw the graph that results from the reduction of 3-SAT to vertex cover | Draw the graph that results from the reduction of 3-SAT to vertex cover | ||
for the expression | for the expression | ||
− | + | <math>(x+ \overline y +z) \cdot (\overline x+y+\overline z) \cdot(\overline x+y+z) \cdot (x+\overline y + \overline x) </math> | |
− | + | <br>9-3. | |
Suppose we are given a subroutine which can solve the | Suppose we are given a subroutine which can solve the | ||
traveling salesman decision problem of | traveling salesman decision problem of | ||
Line 27: | Line 27: | ||
[[TADM2E 9.3|(Solution 9.3)]] | [[TADM2E 9.3|(Solution 9.3)]] | ||
− | + | <br>9-4. | |
Implement a translator that translates satisfiability instances | Implement a translator that translates satisfiability instances | ||
into equivalent 3-SAT instances. | into equivalent 3-SAT instances. | ||
− | + | <br>9-5. | |
Design and implement a backtracking algorithm to test whether | Design and implement a backtracking algorithm to test whether | ||
a set of formulae are satisfiable. | a set of formulae are satisfiable. | ||
Line 38: | Line 38: | ||
[[TADM2E 9.5|(Solution 9.5)]] | [[TADM2E 9.5|(Solution 9.5)]] | ||
− | + | <br>9-6. | |
Implement the vertex cover to satisfiability reduction, and run | Implement the vertex cover to satisfiability reduction, and run | ||
the resulting clauses through a satisfiability testing code. | the resulting clauses through a satisfiability testing code. | ||
Line 47: | Line 47: | ||
'''Basic Reductions''' | '''Basic Reductions''' | ||
− | + | <br>9-7. | |
− | An instance of the ''set cover'' problem consists of a set | + | An instance of the ''set cover'' problem consists of a set <math>X</math> of <math>n</math> |
− | elements, a family | + | elements, a family <math>F</math> of subsets of <math>X</math>, and an integer <math>k</math>. |
− | The question is, does there exist | + | The question is, does there exist <math>k</math> subsets from <math>F</math> whose union is <math>X</math>? |
− | For example, if | + | 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 | + | 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. | Prove that set cover is NP-complete with a reduction from vertex cover. | ||
[[TADM2E 9.7|(Solution 9.7)]] | [[TADM2E 9.7|(Solution 9.7)]] | ||
− | + | <br>9-8. | |
The ''baseball card collector problem'' is as follows. | The ''baseball card collector problem'' is as follows. | ||
− | Given packets | + | 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 | + | 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 | + | 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 | + | 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 | Prove that the baseball card collector problem is NP-hard using a reduction | ||
from vertex cover. | from vertex cover. | ||
− | + | <br>9-9. | |
The ''low-degree spanning tree problem'' is as follows. | The ''low-degree spanning tree problem'' is as follows. | ||
− | Given a graph | + | 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'' | + | tree such that all vertices in the tree have degree ''at most'' <math>k</math> |
(obviously, only tree edges count towards the degree)? | (obviously, only tree edges count towards the degree)? | ||
For example, in the following graph, there is no spanning tree such that all | For example, in the following graph, there is no spanning tree such that all | ||
Line 76: | Line 76: | ||
\fixedfigsize{pictures/lowdegree.eps}{1.0in} | \fixedfigsize{pictures/lowdegree.eps}{1.0in} | ||
#Prove that the low-degree spanning tree problem is NP-hard with a reduction from Hamiltonian ''path''. | #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 | + | #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. |
[[TADM2E 9.9|(Solution 9.9)]] | [[TADM2E 9.9|(Solution 9.9)]] | ||
− | + | <br>9-10. | |
Show that the following problem is NP-complete: | Show that the following problem is NP-complete: | ||
* ''Problem:'' Dense subgraph | * ''Problem:'' Dense subgraph | ||
− | * ''Input:'' A graph | + | * ''Input:'' A graph <math>G</math>, and integers <math>k</math> and <math>y</math>. |
− | * ''Output:'' Does | + | * ''Output:'' Does <math>G</math> contain a subgraph with exactly <math>k</math> vertices and at least <math>y</math> edges? |
− | + | <br>9-11. | |
Show that the following problem is NP-complete: | Show that the following problem is NP-complete: | ||
* ''Problem:'' Clique, no-clique | * ''Problem:'' Clique, no-clique | ||
− | * ''Input:'' An undirected graph | + | * ''Input:'' An undirected graph <math>G=(V,E)</math> and an integer <math>k</math>. |
− | * ''Output:'' Does | + | * ''Output:'' Does <math>G</math> contain both a clique of size <math>k</math> and an independent set of size <math>k</math>. |
[[TADM2E 9.11|(Solution 9.11)]] | [[TADM2E 9.11|(Solution 9.11)]] | ||
− | + | <br>9-12. | |
An ''Eulerian cycle'' is a tour that visits every edge in | An ''Eulerian cycle'' is a tour that visits every edge in | ||
a graph exactly once. | a graph exactly once. | ||
Line 108: | Line 108: | ||
'''Creative Reductions''' | '''Creative Reductions''' | ||
− | + | <br>9-13. | |
Prove that the following problem is NP-complete: | Prove that the following problem is NP-complete: | ||
* ''Problem:'' Hitting Set | * ''Problem:'' Hitting Set | ||
− | * ''Input:'' A collection | + | * ''Input:'' A collection <math>C</math> of subsets of a set <math>S</math>, positive integer <math>k</math>. |
− | * ''Output:'' Does | + | * ''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>? |
[[TADM2E 9.13|(Solution 9.13)]] | [[TADM2E 9.13|(Solution 9.13)]] | ||
− | + | <br>9-14. | |
Prove that the following problem is NP-complete: | Prove that the following problem is NP-complete: | ||
* ''Problem:'' Knapsack | * ''Problem:'' Knapsack | ||
− | * ''Input:'' A set | + | * ''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 | + | * ''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.) | (Hint: start from integer partition.) | ||
− | + | <br>9-15. | |
Prove that the following problem is NP-complete: | Prove that the following problem is NP-complete: | ||
* ''Problem:'' Hamiltonian Path | * ''Problem:'' Hamiltonian Path | ||
− | * ''Input:'' A graph | + | * ''Input:'' A graph <math>G</math>, and vertices <math>s</math> and <math>t</math>. |
− | * ''Output:'' Does | + | * ''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.) | (Hint: start from Hamiltonian cycle.) | ||
[[TADM2E 9.15|(Solution 9.15)]] | [[TADM2E 9.15|(Solution 9.15)]] | ||
− | + | <br>9-16. | |
Prove that the following problem is NP-complete: | Prove that the following problem is NP-complete: | ||
* ''Problem:'' Longest Path | * ''Problem:'' Longest Path | ||
− | * ''Input:'' A graph | + | * ''Input:'' A graph <math>G</math> and positive integer <math>k</math>. |
− | * ''Output:'' Does | + | * ''Output:'' Does <math>G</math> contain a path that visits at least <math>k</math> different vertices without visiting any vertex more than once? |
− | + | <br>9-17. | |
Prove that the following problem is NP-complete: | Prove that the following problem is NP-complete: | ||
* ''Problem:'' Dominating Set | * ''Problem:'' Dominating Set | ||
− | * ''Input:'' A graph | + | * ''Input:'' A graph <math>G=(V,E)</math> and positive integer <math>k</math>. |
− | * ''Output:'' Is there a subset | + | * ''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>. |
[[TADM2E 9.17|(Solution 9.17)]] | [[TADM2E 9.17|(Solution 9.17)]] | ||
− | + | <br>9-18. | |
− | Prove that the vertex cover problem (does there exist a subset | + | Prove that the vertex cover problem (does there exist a subset <math>S</math> of <math>k</math> |
− | vertices in a graph | + | vertices in a graph <math>G</math> such that every edge in <math>G</math> is incident upon |
− | at least one vertex in | + | 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. | the graph are restricted to have even degrees. | ||
− | + | <br>9-19. | |
Prove that the following problem is NP-complete: | Prove that the following problem is NP-complete: | ||
* ''Problem:'' Set Packing | * ''Problem:'' Set Packing | ||
− | * ''Input:'' A collection | + | * ''Input:'' A collection <math>C</math> of subsets of a set <math>S</math>, positive integer <math>k</math>. |
− | * ''Output:'' Does | + | * ''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?) |
[[TADM2E 9.19|(Solution 9.19)]] | [[TADM2E 9.19|(Solution 9.19)]] | ||
− | + | <br>9-20. | |
Prove that the following problem is NP-complete: | Prove that the following problem is NP-complete: | ||
* ''Problem:'' Feedback Vertex Set | * ''Problem:'' Feedback Vertex Set | ||
− | * ''Input:'' A directed graph | + | * ''Input:'' A directed graph <math>G=(V,A)</math> and positive integer <math>k</math>. |
− | * ''Output:'' Is there a subset | + | * ''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? |
Line 170: | Line 170: | ||
'''Algorithms for Special Cases''' | '''Algorithms for Special Cases''' | ||
− | + | <br>9-21. | |
− | A Hamiltonian path | + | A Hamiltonian path <math>P</math> is a path |
that visits each vertex exactly once. | that visits each vertex exactly once. | ||
− | The problem of testing whether a graph | + | The problem of testing whether a graph <math>G</math> contains a |
Hamiltonian path is NP-complete. | Hamiltonian path is NP-complete. | ||
There does not have to be an | There does not have to be an | ||
− | edge in | + | edge in <math>G</math> from the ending vertex to the starting vertex of <math>P</math>, unlike |
in the Hamiltonian cycle problem. | in the Hamiltonian cycle problem. | ||
− | Give an | + | Give an <math>O(n+m)</math>-time |
− | algorithm to test whether a directed acyclic graph | + | algorithm to test whether a directed acyclic graph <math>G</math> (a DAG) |
contains a Hamiltonian path. | contains a Hamiltonian path. | ||
(Hint: think about topological sorting and DFS.) | (Hint: think about topological sorting and DFS.) | ||
Line 185: | Line 185: | ||
[[TADM2E 9.21|(Solution 9.21)]] | [[TADM2E 9.21|(Solution 9.21)]] | ||
− | + | <br>9-22. | |
− | The | + | The <math>2</math>-SAT problem is, given a Boolean formula in 2-conjunctive normal form |
(CNF), to decide whether the formula is satisfiable. | (CNF), to decide whether the formula is satisfiable. | ||
− | + | <math>2</math>-SAT is like <math>3</math>-SAT, except that each clause can have only two literals. | |
− | For example, the following formula is in | + | For example, the following formula is in <math>2</math>-CNF: |
− | + | <math> (x_1 \vee x_2) \wedge (\bar{x}_2 \vee x_3) \wedge (x_1 \vee \bar{x}_3) </math> | |
− | Give a polynomial-time algorithm to solve | + | Give a polynomial-time algorithm to solve <math>2</math>-SAT. |
Line 197: | Line 197: | ||
'''P=NP?''' | '''P=NP?''' | ||
− | + | <br>9-23. | |
Show that the following problems are in NP: | Show that the following problems are in NP: | ||
− | #Does graph | + | #Does graph <math>G</math> have a simple path (i.e., with no vertex repeated) of length <math>k</math>? |
− | #Is integer | + | #Is integer <math>n</math> composite (i.e., not prime)? |
− | #Does graph | + | #Does graph <math>G</math> have a vertex cover of size <math>k</math>? |
[[TADM2E 9.23|(Solution 9.23)]] | [[TADM2E 9.23|(Solution 9.23)]] | ||
− | + | <br>9-24. | |
− | It was a long open question whether the decision problem ''Is integer | + | It was a long open question whether the decision problem ''Is integer <math>n</math> a composite number, in other words, not prime?'' can be computed in |
time polynomial in the size of its input. | time polynomial in the size of its input. | ||
Why doesn't the following algorithm suffice to prove it is in P, | Why doesn't the following algorithm suffice to prove it is in P, | ||
− | since it runs in | + | since it runs in <math>O(n)</math> time? |
− | PrimalityTesting( | + | PrimalityTesting(<math>n</math>) |
− | composite := | + | composite := <math>false</math> |
− | for i := 2 to | + | for i := 2 to <math>n-1</math> do |
− | if | + | if <math>(n\,\bmod\,i) = 0</math> then |
− | composite := | + | composite := <math>true</math> |
'''Approximation Algorithms''' | '''Approximation Algorithms''' | ||
− | + | <br>9-25. | |
In the ''maximum-satisfiability problem'', we seek a truth assignment that | In the ''maximum-satisfiability problem'', we seek a truth assignment that | ||
satisfies as many clauses as possible. | satisfies as many clauses as possible. | ||
Line 227: | Line 227: | ||
[[TADM2E 9.25|(Solution 9.25)]] | [[TADM2E 9.25|(Solution 9.25)]] | ||
− | + | <br>9-26. | |
Consider the following heuristic for vertex cover. | Consider the following heuristic for vertex cover. | ||
Construct a DFS tree of the graph, and delete all the leaves from this tree. | Construct a DFS tree of the graph, and delete all the leaves from this tree. | ||
Line 233: | Line 233: | ||
Prove that the size of this cover is at most twice as large as optimal. | Prove that the size of this cover is at most twice as large as optimal. | ||
− | + | <br>9-27. | |
− | The ''maximum cut'' problem for a graph | + | The ''maximum cut'' problem for a graph <math>G=(V,E)</math> seeks to partition |
− | the vertices | + | the vertices <math>V</math> into disjoint sets <math>A</math> and <math>B</math> so as to maximize the |
− | number of edges | + | number of edges <math>(a,b) \in E</math> such that <math>a \in A</math> and <math>b \in B</math>. |
Consider the following heuristic for max cut. | Consider the following heuristic for max cut. | ||
− | First assign | + | First assign <math>v_1</math> to <math>A</math> and <math>v_2</math> to <math>B</math>. |
For each remaining vertex, assign it to the side that adds the most edges | For each remaining vertex, assign it to the side that adds the most edges | ||
to the cut. | to the cut. | ||
Line 245: | Line 245: | ||
[[TADM2E 9.27|(Solution 9.27)]] | [[TADM2E 9.27|(Solution 9.27)]] | ||
− | + | <br>9-28. | |
− | In the ''bin-packing problem'', we are given | + | In the ''bin-packing problem'', we are given <math>n</math> items |
− | with weights | + | with weights <math>w_1,w_2,...,w_n</math>, respectively. |
Our goal is to find the smallest | Our goal is to find the smallest | ||
− | number of bins that will hold the | + | number of bins that will hold the <math>n</math> objects, |
where each bin has capacity of at most one kilogram. | where each bin has capacity of at most one kilogram. | ||
The ''first-fit heuristic'' | The ''first-fit heuristic'' | ||
Line 259: | Line 259: | ||
solution. | solution. | ||
− | + | <br>9-29. | |
For the first-fit heuristic described just above, give an example where the packing | For the first-fit heuristic described just above, give an example where the packing | ||
− | it fits uses at least | + | it fits uses at least <math>5/3</math> times as many bins as optimal. |
[[TADM2E 9.29|(Solution 9.29)]] | [[TADM2E 9.29|(Solution 9.29)]] | ||
− | + | <br>9-30. | |
− | A ''vertex coloring'' of graph | + | A ''vertex coloring'' of graph <math>G=(V,E)</math> is an assignment of colors to vertices |
− | of | + | of <math>V</math> such that each edge <math>(x,y)</math> implies that vertices <math>x</math> and |
− | + | <math>y</math> are assigned different colors. | |
− | Give an algorithm for vertex coloring | + | Give an algorithm for vertex coloring <math>G</math> using at most <math>\Delta+1</math> |
− | colors, where | + | colors, where <math>\Delta</math> is the maximum vertex degree of <math>G</math>. |
Revision as of 18:23, 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) $
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.
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?
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.
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}
- 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 $ 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.
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 $.
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' $?
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.)
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' $.
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?)
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.)
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:
- Does graph $ G $ have a simple path (i.e., with no vertex repeated) of length $ k $?
- Is integer $ n $ composite (i.e., not prime)?
- Does graph $ G $ have a vertex cover of size $ k $?
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.
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.
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.
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 $.