# Difference between revisions of "Chapter 12"

=Dealing with Hard Problems=\

## Contents

### Special Cases of Hard Problems

12.1. Dominos are tiles represented by integer pairs $(x_{i},y_{i})$ , where each of the values $x_{i}$ and $y_{i}$ are integers between 1 and $n$ . Let $S$ be a sequence of m integer pairs $[(x_{1},y_{1}),(x_{2},y_{2}),...,(x_{m},y_{m})]$ . The goal of the game is to create long chains $[(x_{i1},y_{i1}),(x_{i2},y_{i2}),...,(x_{it},y_{it})]$ such that $y_{ij}=x_{i(j+1)}$ . Dominos can be flipped, so $(x_{i},y_{i})$ equivalent to $(y_{i},x_{i})$ . For $S=[(1,3),(4,2),(3,5),(2,3),(3,8)]$ , the longest domino sequences include $[(4,2),(2,3),(3,8)]$ and $[(1,3),(3,2),(2,4)]$ .
(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 $[(1,3),(3,5)]$ and $[(2,3),(3,5)]$ .

12.2. Let $G=(V,E)$ be a graph and $x$ and $y$ be two distinct vertices of $G$ . Each vertex $v$ contains a given number of tokens $t(v)$ that you can collect if you visit $v$ .
(a) Prove that it is NP-complete to find the path from $x$ to $y$ where you can collect the greatest possible number of tokens.
(b) Give an efficient algorithm if $G$ is a directed acyclic graph (DAG).

12.3. The Hamiltonian completion problem takes a given graph $G$ and seeks an algorithm to add the smallest number of edges to $G$ so that it contains a Hamiltonian cycle. This problem is NP-complete for general graphs; however, it has an efficient algorithm if $G$ is a tree. Give an efficient and provably correct algorithm to add the minimum number of possible edges to tree $T$ so that $T$ plus these edges is Hamiltonian.

12.4

12.5

12.6

12.7

12.8

12.9

12.10

12.11

12.12

12.13

12.14

12.15

12.16

12.17

12.18

### "Quantum" Computing

12.19

12.20

12.21

12.22

Back to Chapter List