# Chapter 12

=Dealing with Hard Problems=\

## Contents

### Special Cases of Hard Problems

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

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

12.3. The Hamiltonian completion problem takes a given graph ${\displaystyle G}$ and seeks an algorithm to add the smallest number of edges to ${\displaystyle G}$ so that it contains a Hamiltonian cycle. This problem is NP-complete for general graphs; however, it has an efficient algorithm if ${\displaystyle G}$ is a tree. Give an efficient and provably correct algorithm to add the minimum number of possible edges to tree ${\displaystyle T}$ so that ${\displaystyle 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