# Chapter 12

Revision as of 20:30, 10 September 2020 by Algowikiadmin (talk | contribs) (→Special Cases of Hard Problems)

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

- 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