12.1

(a) NP–completeness
  Decision version (DOMINO-PATH):
  “Given a multiset S of dominos and an integer k, does S contain a chain of at least k tiles?”

1  Membership in NP – a certificate is the ordered list of k dominos (together with their chosen orientations); in O(k) time we check that
    y_i=x_i+1 for every consecutive pair and that no tile is used twice.

2  NP–hardness – reduction from Hamiltonian path in a directed graph (HP), known to be NP-complete.
 Given a directed graph G=(V,E), label the |V| vertices 1…n.  For every arc (u,v)∈E create one domino (u,v).  Let k=n−1.  Because each domino keeps the orientation of its arc, a domino chain of length k is exactly a directed path that visits k+1 vertices; this is a Hamiltonian path ⇔ HP has a solution.  The construction is clearly polynomial, so DOMINO-PATH is NP-hard and therefore NP-complete.

(b) Longest chain with strictly increasing numbers
 Orient every domino from the smaller to the larger number; e.g. (5,2) becomes the arc 2→5.  The resulting graph is a DAG on vertices 1…n, possibly with parallel edges.  In a DAG the longest path can be found in linear time by dynamic programming over a topological order, which here is simply 1,2,…,n.

# S = list of dominos (a,b)
A = { } # adjacency lists
for (a,b) in S:
  u,v = min(a,b), max(a,b)
  A.setdefault(u, []).append((u,v))
dp = [0]*(n+1) # longest length ending in vertex i
pred = [None]*(n+1) # predecessor of i on that path
for u in range(1,n+1):
  for (u,v) in A.get(u,[]):
    if dp[v] < dp[u]+1:
      dp[v] = dp[u]+1
      pred[v] = u
t = argmax(dp) # end vertex of the longest chain
chain = []
while pred[t] is not None:
  chain.append((pred[t],t))
  t = pred[t]
chain.reverse()

• Time complexity: Θ(n+m) with n≤max label, m=|S|.
• Space: Θ(n+m).

Applied to S = {(1,3),(4,2),(3,5),(2,3),(3,8)} the algorithm returns the two maximal increasing chains
  [(1,3),(3,5)] and [(2,3),(3,5)], each of length 2.

Back to Chapter 12