Algorithm for finding a Hamiltonian path in a DAG

Question

Consider a directed acyclic graph (DAG) $G$ with $n$ vertices that does not possess a Hamiltonian path.

Which algorithm can be employed to determine the minimum number of additional edges required to establish a Hamiltonian path while preserving the acyclic nature of the graph $G$?

Answer 1

Let $k$ be the smallest number of directed, vertex disjoint paths in the DAG such that every vertex is adjacent to some path edge; in this context also paths with a single vertex are allowed; then the number of edges that must be added to generate a Hamilton path is $k-1$.

The calculation of such a minimal number of paths in the DAG is also efficiently possible:

• split the vertices $v$ in $v_\tau$ and $v_\sigma$, its roles as target vertex and as source vertex of directed edges.
• connect $v_\tau$ and $v_\sigma$ with the directed edge $(v_\tau,v_\sigma)$ of weight $0$
• if $u_\sigma$ comes before $v_\tau$ on some directed path in the DAG then connect $v_\tau$ with $u_\sigma$ with the directed edge $(v_\tau,u_\sigma)$ with very high weight $\mathrm{INF}$
• associate each edge with flow constraints: a capacity of $1$ for every edge of the resulting graph and a lower bound of $1$ for edges that connect splitted vertices and $0$ for all other edges calculate the mincost flow in $G$
• remove from the edges with nonzero flow all edges of weight $\mathrm{INF}$
• connect the resulting directed paths in the obvious way by $k-1$ directed edges