# Bottleneck $k$-link path in a complete DAG

Let $$G$$ be a complete DAG: It has vertices $$v_1,\ldots,v_n$$, and $$v_iv_j$$ is an edge if and only if $$i. Let $$w(i,j)$$ be the weight of the edge $$v_iv_j$$. The weight has the property that $$w(i,j) and $$w(i+1,j).

We are given an integer $$k$$. We are interested in finding the minimum $$\lambda$$, such that there exists a path of length $$k$$ from $$v_1$$ to $$v_n$$, such that each edge in the path has weight at most $$\lambda$$. Let the optimal value be $$\lambda^*$$.

Assume one has an oracle that takes $$i,j$$ and output $$w(i,j)$$. One does not have to inspect the entire graph in order to find $$\lambda^*$$.

First, given a $$\lambda$$, we can decide if $$\lambda < \lambda^*$$ in $$O(n)$$ time using a greedy algorithm.

Second, consider the sorted list of elements in $$S= \{w(i,j) | 1\leq i. $$\lambda^*\in S$$. One can select the $$i$$th largest value in $$S$$ in $$O(n)$$ time, because $$w(i,j)$$ forms a matrix sorted in both row and column (For example, see this). Hence we can do binary search over the elements in $$S$$, which takes in $$O(n\log n)$$ time. ($$\log n$$ iterations, and $$O(n)$$ time to get the ith element)

Is there a faster algorithm?

• In order to binary search the value of $\lambda$, wouldn't you need to do log of the max possible value of lambda comparisons rather than log n? – Mikhail Rudoy Jan 29 at 20:22
• I've made some updates. The log is over the possible values of $\lambda$, which is bounded by $O(n^2)$. – Chao Xu Jan 29 at 20:34