11.31

Idea. In a DAG every Hamiltonian path is a topological ordering [math](v_1,\dots ,v_n)[/math] in which every consecutive pair is joined by an edge [math]v_i\to v_{i+1}[/math]. Conversely, such a topological order exists iff while we build the order there is never more than one current source (vertex whose in-degree is 0): if two different sources existed, no edge could go from one to the other, so they could never be adjacent in a Hamiltonian path.

Algorithm (Kahn-style topological sort).

in_deg[v] = # incoming edges of v S = {v | in_deg[v]=0} # current sources path = [] # will store the ordering while S is not empty: if |S| > 1: return “NO Hamiltonian path” u = the single vertex in S append u to path for each edge u → w: in_deg[w] –= 1 if in_deg[w] == 0: add w to S return “YES” and path # path is Hamiltonian

Correctness. • If the algorithm answers “YES”, every vertex that becomes the unique source did so only after its single predecessor was removed, hence that predecessor has an edge to it; the produced order is therefore a Hamiltonian path.
• If it answers “NO”, at some step two sources a and b are simultaneously present. Neither has incoming edges, so neither can reach the other, meaning no ordering can put them consecutively with an edge between them. Thus no Hamiltonian path exists.

Complexity. Each vertex enters the queue once and each edge is examined once, so the running time is [math]O(n+m)[/math] and the memory usage is [math]O(n)[/math].

Back to Chapter 11