Finding a Shortest M-link Path in a Monge Directed Acyclic Graph

A Monge directed acyclic graph (DAG) G on the nodes 1,2,⋯,N has edges ( i,j) for 1≤ i<j≤ N carrying submodular edge-lengths. Finding a shortest M-link path from $1$ to N in G for any given $1<M<N-1$ has many applications. In this paper, we give a contract-and-conquer algorithm for this problem which runs in O( √NM( N-M) log( N-M) ) time and O( N) space. It is the first o( NM)-time algorithm with linear space complexity, and its time complexity decreases with M when M≥ N/2. In contrast, all previous strongly polynomial algorithms have running time growing with M. For both O( poly( log N) ) and N-O( poly( log N) ) regimes of M, our algorithm has running time O( N· poly( log N) ), which partially answers an open question rased in {AST94} affirmatively.