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

A Monge directed acyclic graph (DAG) $G$ on the nodes $1,2,\cdots ,N$ has edges $(i,j)$ for $1\le i<j\le 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\left(\sqrt{NM(N-M)\log (N-M)}\right)$ time and $O\left(N\right)$ space. It is the first $o\left(NM\right)$-time algorithm with linear space complexity, and its time complexity decreases with $M$ when $M\ge N\mathrm{/}2$. In contrast, all previous strongly polynomial algorithms have running time growing with $M$. For both $O\left(poly(\log N)\right)$ and $N-O\left(poly(\log N)\right)$ regimes of $M$, our algorithm has running time $O(N\cdot poly(\log N))$, which partially answers an open question rased in \cite{AST94} affirmatively.