= Subset dynamic programming for a Hamiltonian path
{title2=$D[S,v]=\bigvee_{u\in S\setminus\{v\}}(D[S\setminus\{v\},u]\land A[u,v])$}
For a <directed graph> with <adjacency matrix> $A$, let $D[S,v]$ record whether a path visits precisely the <vertices> of $S$ once and ends at $v$. The singleton states are true. A larger state is true exactly when some predecessor $u\in S\setminus\{v\}$ has a true state for $S\setminus\{v\}$ and an edge to $v$. Removing or adjoining the last edge proves this recurrence by <mathematical induction> on $|S|$. There are $n2^{n-1}$ states, each requiring at most $n-1$ predecessor checks, giving $O(n^22^n)$ time and $O(n2^n)$ storage. A true state for $S=V$ certifies a <Hamiltonian path>.
Back to article page
