A DAG is called complete, if there are vertices $v_1,\dots ,v_n$, and $v_i{v}_j$ is an edge if and only if $i<j$. Let $w(i,j)$ be the edge weights from $i$ to $j$. The weight is called ordered, if $w(i,j)<w(i,j+1)$ and $w(i+1,j)<w(i,j)$.

One can formulate a dynamic programming algorithm, which takes $O(k{n}^2)$ time. My previous writing shows an $O(kn)$ time algorithm using the monge property. Using binary search, there is also an $O(k\log (n/k)\log M)$ time algorithm if all weights are positive integers no larger than $M$.

We show there is an $O(n+k\log (n/k)\log n)$ time algorithm. Assume ${\lambda }^{\ast }$ is the optimal weight. First, there is an oracle that given $\lambda$, decides if $\lambda \ge {\lambda }^{\ast }$. Indeed, we can apply the greedy algorithm. Find the sequence $a_1,\dots ,a_k$, as follows. $a_0=1$, $a_i$ is the largest value such that $w(a_{i-1},a_i)\le \lambda$. If $a_k=n$, then it is clear that $\lambda \ge {\lambda }^{\ast }$. Also, we can show if $a_k<n$, then $\lambda <{\lambda }^{\ast }$. $O(n)$ time seems to be a quite large bound. We could do it in $O(k\log (n))$ instead by doing binary search for each $a_i$. Using exponential search instead, we can obtain a $O(k\log (n/k))$ time algorithm.

One need to do binary search for ${\lambda }^{\ast }$. There are $\Omega (n^2)$ weights, let it be $W$. One does not have to know all of them in order to apply binary search. Note that $w$ is a matrix sorted in both row and column, hence we need a selection algorithm that returns the $k$th smallest element for such matrix. There is an $O(n)$ time algorithm for that. Hence we can do binary search on the sorted $W$ by spending $O(n)$ time to access $i$th element. We now obtain a $O((n+k\log (n/k))\log n)=O(n\log n)$ time algorithm. Not bad.

We can speed it up even further. Instead of selection in the sorted matrix, we can do search in the sorted matrix. We are given an oracle to test if a value is smaller than ${\lambda }^{\ast }$ after all. We can do search for ${\lambda }^{\ast }$ using $O(\log n)$ oracle calls and $O(n)$ time. Hence this gives us a $O(n+k\log (n/k)\log n)$ time algorithm for the problem. Whenever $k=O(\frac{n}{\log (n)\log \log n})$, this is $O(n)$ time.

As an application, we obtain a solution to Leetcode 410 Split Array Largest Sum. The problem is also called the linear partitioning problem. The problem asks one to partition array into $k$ contagious subarrays that minimizes the maximum sum of each subarray. It was an example for learning dynamic programming in chapter 8.5 of [1]. An $O(k{n}^2)$ algorithm was given. Reading the discussion online, one would find $O(n\log M)$ time algorithm is the suggested solution, where $M$ is the maximum over all integers. The algorithm is actually fairly useful for photo galleries. There is the NPM package linear-partitioning, used by multiple photo galleries packages. My first encountered of the problem was also for photo gallery. The linear partition problem reduces to the bottleneck $k$-link path problem because we can define $w(i,j)$ to be the sum of elements from the $i$th index of the array to the $j$th index of the array. After $O(n)$ preprocessing, $w(i,j)$ can be computed in $O(1)$ time. This results a $O(n+k\log (n/k)\log n)$ running time algorithm.

What about when $k$ is large? I’ve emailed Samson Zhou, who has confirmed the algorithm in [2] can be used to solve the problem in $O(n)$ time.

References