<p>Let <span class="math-container">$G$</span> be a complete DAG: It has vertices <span class="math-container">$v_1,\ldots,v_n$</span>, and <span class="math-container">$v_iv_j$</span> is an edge if and only if <span class="math-container">$i&lt;j$</span>. 
Let <span class="math-container">$w(i,j)$</span> be the weight of the edge <span class="math-container">$v_iv_j$</span>. The weight has the property that <span class="math-container">$w(i,j)&lt;w(i,j+1)$</span> and <span class="math-container">$w(i+1,j)&lt;w(i,j)$</span>.</p>

<p>We are given an integer <span class="math-container">$k$</span>. We are interested in finding the minimum <span class="math-container">$\lambda$</span>, such that there exists a path of length <span class="math-container">$k$</span> from <span class="math-container">$v_1$</span> to <span class="math-container">$v_n$</span>, such that each edge in the path has weight at most <span class="math-container">$\lambda$</span>.
Let the optimal value be <span class="math-container">$\lambda^*$</span>.</p>

<p>Assume one has an oracle that takes <span class="math-container">$i,j$</span> and output <span class="math-container">$w(i,j)$</span>. One does not have to inspect the entire graph in order to find <span class="math-container">$\lambda^*$</span>.</p>

<p>First, given a <span class="math-container">$\lambda$</span>, we can decide if <span class="math-container">$\lambda &lt; \lambda^*$</span> in <span class="math-container">$O(n)$</span> time using a greedy algorithm.</p>

<p>Second, consider the sorted list of elements in <span class="math-container">$S= \{w(i,j) | 1\leq i&lt;j\leq n\}$</span>. <span class="math-container">$\lambda^*\in S$</span>. One can select the <span class="math-container">$i$</span>th largest value in <span class="math-container">$S$</span> in <span class="math-container">$O(n)$</span> time, because <span class="math-container">$w(i,j)$</span> forms a matrix sorted in both row and column (For example, see <a href="https://www.sciencedirect.com/science/article/pii/0020019085901231" rel="nofollow noreferrer">this</a>). Hence we can do binary search over the elements in <span class="math-container">$S$</span>, which takes in <span class="math-container">$O(n\log n)$</span> time. (<span class="math-container">$\log n$</span> iterations, and <span class="math-container">$O(n)$</span> time to get the ith element)</p>

<p>Is there a faster algorithm? </p>

CC BY-SA 4.0
2019-01-29T20:22:05.437Z
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
CC BY-SA 4.0
2019-01-29T20:34:07.620Z
I've made some updates. The log is over the possible values of $\lambda$, which is bounded by $O(n^2)$.
Chao Xu
<ds.algorithms>
Bottleneck $k$-link path in a complete DAG
Chao Xu
# Bottleneck $k$-link path in a complete DAG

(Asked by: username_0 on 2019-01-28)

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](https://www.sciencedirect.com/science/article/pii/0020019085901231)). 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?

**Tags:** ds.algorithms
> **Comments:**
> **username_1**: 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?  
> **username_0**: I've made some updates. The log is over the possible values of $\lambda$, which is bounded by $O(n^2)$.  

---

## 0 answers

