# Bottleneck $k$-link path

A DAG is called complete, if there are vertices $v_{1},…,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)$.

Find a path consists of $k$ edges from $v_{1}$ to $v_{n}$, such that the maximum weight of the edges in the path is minimized.

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

We show there is an $O(n+kg(n/k)gn)$ time algorithm. Assume $λ_{∗}$ is the optimal weight. First, there is an oracle that given $λ$, decides if $λ≥λ_{∗}$. Indeed, we can apply the greedy algorithm. Find the sequence $a_{1},…,a_{k}$, as follows. $a_{0}=1$, $a_{i}$ is the largest value such that $w(a_{i−1},a_{i})≤λ$. If $a_{k}=n$, then it is clear that $λ≥λ_{∗}$. Also, we can show if $a_{k}<n$, then $λ<λ_{∗}$. $O(n)$ time seems to be a quite large bound. We could do it in $O(kg(n))$ instead by doing binary search for each $a_{i}$. Using exponential search instead, we can obtain a $O(kg(n/k))$ time algorithm.

One need to do binary search for $λ_{∗}$. There are $Ω(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+kg(n/k))gn)=O(ngn)$ 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 $λ_{∗}$ after all. We can do search for $λ_{∗}$ using $O(gn)$ oracle calls and $O(n)$ time. Hence this gives us a $O(n+kg(n/k)gn)$ time algorithm for the problem. Whenever $k=O(log(n)loglognn )$, 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(kn_{2})$ algorithm was given. Reading the
discussion online, one would find $O(ngM)$ 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+kg(n/k)gn)$ 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

**The algorithm design manual**, Springer, 2010.

**Optimal parametric search for path and tree partitioning**, CoRR. abs/1711.00599 (2017).