Difference between revisions of "Chapter 12"
Jump to navigation
Jump to search
| Line 3: | Line 3: | ||
===Special Cases of Hard Problems=== | ===Special Cases of Hard Problems=== | ||
| − | :[[12.1]] | + | :[[12.1]]. Dominos are tiles represented by integer pairs <math>(x_i, y_i)</math>, where each of the values <math>x_i</math> and <math>y_i</math> are integers between 1 and <math>n</math>. Let <math>S</math> be a sequence of m integer pairs <math>[(x_1, y_1),(x_2, y_2), ...,(x_m, y_m)]</math>. The goal of the game is to create long chains <math>[(x_{i1}, y_{i1}),(x_{i2}, y_{i2}), ...,(x_{it}, y_{it})]</math> such that <math>y_{ij} = x_{i(j+1)}</math>. Dominos can be flipped, so <math>(x_i, y_i)</math> equivalent to <math>(y_i, x_i)</math>. For <math>S = [(1, 3),(4, 2),(3, 5),(2, 3),(3, 8)]</math>, the longest domino sequences include <math>[(4, 2),(2, 3),(3, 8)]</math> and <math>[(1, 3),(3, 2),(2, 4)]</math>. |
| + | ::(a) Prove that finding the longest domino chain is NP-complete. | ||
| + | ::(b) Give an efficient algorithm to find the longest domino chain where the numbers increase along the chain. For S above, the longest such chains are <math>[(1, 3),(3, 5)]</math> and <math>[(2, 3),(3, 5)]</math>. | ||
| + | [[12.1|Solution]] | ||
| − | :12.2 | + | :12.2. Let <math>G = (V, E)</math> be a graph and <math>x</math> and <math>y</math> be two distinct vertices of <math>G</math>. Each vertex <math>v</math> contains a given number of tokens <math>t(v)</math> that you can collect if you visit <math>v</math>. |
| + | ::(a) Prove that it is NP-complete to find the path from <math>x</math> to <math>y</math> where you can collect the greatest possible number of tokens. | ||
| + | ::(b) Give an efficient algorithm if <math>G</math> is a directed acyclic graph (DAG). | ||
| − | :[[12.3]] | + | :[[12.3]]. The ''Hamiltonian completion problem'' takes a given graph <math>G</math> and seeks an algorithm to add the smallest number of edges to <math>G</math> so that it contains a Hamiltonian cycle. This problem is NP-complete for general graphs; however, it has an efficient algorithm if <math>G</math> is a tree. Give an efficient and provably correct algorithm to add the minimum number of possible edges to tree <math>T</math> so that <math>T</math> plus these edges is Hamiltonian. |
| − | + | [[12.3|Solution]] | |
===Approximation Algorithms=== | ===Approximation Algorithms=== | ||
Revision as of 20:30, 10 September 2020
=Dealing with Hard Problems=\
Contents
Special Cases of Hard Problems
- 12.1. Dominos are tiles represented by integer pairs , where each of the values and are integers between 1 and . Let be a sequence of m integer pairs . The goal of the game is to create long chains such that . Dominos can be flipped, so equivalent to . For , the longest domino sequences include and .
- (a) Prove that finding the longest domino chain is NP-complete.
- (b) Give an efficient algorithm to find the longest domino chain where the numbers increase along the chain. For S above, the longest such chains are and .
![{\displaystyle [(x_{1},y_{1}),(x_{2},y_{2}),...,(x_{m},y_{m})]}](https://en.wikipedia.org/api/rest_v1/media/math/render/svg/e6add16453cd4d68cb1502231b34b4e3e0408bd4)
![{\displaystyle [(x_{i1},y_{i1}),(x_{i2},y_{i2}),...,(x_{it},y_{it})]}](https://en.wikipedia.org/api/rest_v1/media/math/render/svg/c547a1a6db3aa8da2d3c896818293907cd1fe338)
![{\displaystyle S=[(1,3),(4,2),(3,5),(2,3),(3,8)]}](https://en.wikipedia.org/api/rest_v1/media/math/render/svg/5adaa38b69878b2573df0f7173a223850dfae107)
![{\displaystyle [(4,2),(2,3),(3,8)]}](https://en.wikipedia.org/api/rest_v1/media/math/render/svg/a3995d9e2db2306ade8f1e710c9f8f55ef981f7d)
![{\displaystyle [(1,3),(3,2),(2,4)]}](https://en.wikipedia.org/api/rest_v1/media/math/render/svg/efea86e48df11ac04cc4736671c783119883b59e)
![{\displaystyle [(1,3),(3,5)]}](https://en.wikipedia.org/api/rest_v1/media/math/render/svg/acc3f4136cd3137c91c138b93fbe1d0135c6e97f)
![{\displaystyle [(2,3),(3,5)]}](https://en.wikipedia.org/api/rest_v1/media/math/render/svg/67fffc643de3153a9ede4af96b17b06dc12d9b2e)
- 12.2. Let be a graph and and be two distinct vertices of . Each vertex contains a given number of tokens that you can collect if you visit .
- (a) Prove that it is NP-complete to find the path from to where you can collect the greatest possible number of tokens.
- (b) Give an efficient algorithm if is a directed acyclic graph (DAG).
- 12.3. The Hamiltonian completion problem takes a given graph and seeks an algorithm to add the smallest number of edges to so that it contains a Hamiltonian cycle. This problem is NP-complete for general graphs; however, it has an efficient algorithm if is a tree. Give an efficient and provably correct algorithm to add the minimum number of possible edges to tree so that plus these edges is Hamiltonian.
Approximation Algorithms
- 12.4
- 12.6
- 12.8
- 12.10
Combinatorial Optimization
- 12.12
- 12.14
- 12.16
- 12.18
"Quantum" Computing
- 12.20
- 12.22
Back to Chapter List
