6
$\begingroup$

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?

$\endgroup$
  • 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 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 at 20:34

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.