Past exam of the year 1 of the computer science course of the University of Oxford / 2016 / Functional programming, design and analysis of algorithms / 6 / b

Use subset dynamic programming for a Hamiltonian path, with a Boolean dynamic programming state $D[S,v]$ for each nonempty subset $S\subseteq V$ and $v\in S$. It is true exactly when there is a graph path using every vertex of $S$ once, using no other vertices, and ending at $v$. The base and transition arewhere $A$ is the adjacency matrix of a directed graph.For correctness, a valid path ending at $v$ has some penultimate vertex $u$; removing $v$ yields exactly a path recorded by the corresponding predecessor state. Conversely, extending any true predecessor state by the edge $(u,v)$ produces a path visiting precisely $S$ once. Mathematical induction on $|S|$ proves the meaning of every state. Therefore the final disjunction is true exactly when a Hamiltonian path exists.

There are $n{2}^{n-1}$ possible states and at most $n-1$ predecessor checks per state. More exactly, the full set of ordered predecessor checks has size $n(n-1)2^{n-2}$ for $n\ge 2$. With constant-time adjacency matrix access and ordinary subset-indexed table access,The graph is normally assumed nonempty here. If the empty graph is admitted, return the chosen convention for its empty Hamiltonian path separately; it does not affect the bound.