Chapter 12

=Dealing with Hard Problems=\

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

Solution

12.2. Let [math]\displaystyle{ G = (V, E) }[/math] be a graph and [math]\displaystyle{ x }[/math] and [math]\displaystyle{ y }[/math] be two distinct vertices of [math]\displaystyle{ G }[/math]. Each vertex [math]\displaystyle{ v }[/math] contains a given number of tokens [math]\displaystyle{ t(v) }[/math] that you can collect if you visit [math]\displaystyle{ v }[/math].

(a) Prove that it is NP-complete to find the path from [math]\displaystyle{ x }[/math] to [math]\displaystyle{ y }[/math] where you can collect the greatest possible number of tokens.

(b) Give an efficient algorithm if [math]\displaystyle{ G }[/math] is a directed acyclic graph (DAG).

12.3. The Hamiltonian completion problem takes a given graph [math]\displaystyle{ G }[/math] and seeks an algorithm to add the smallest number of edges to [math]\displaystyle{ 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]\displaystyle{ G }[/math] is a tree. Give an efficient and provably correct algorithm to add the minimum number of possible edges to tree [math]\displaystyle{ T }[/math] so that [math]\displaystyle{ T }[/math] plus these edges is Hamiltonian.

Solution