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<j$. Let $w(i,j)$ be the weight of the edge $v_iv_j$. The weight has the property that $w(i,j)<w(i,j+1)$ and $w(i+1,j)<w(i,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<j\leq n\}$. $\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?

  • 1
    $\begingroup$ 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? $\endgroup$ – Mikhail Rudoy Jan 29 '19 at 20:22
  • $\begingroup$ I've made some updates. The log is over the possible values of $\lambda$, which is bounded by $O(n^2)$. $\endgroup$ – Chao Xu Jan 29 '19 at 20:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.