2
$\begingroup$

I have this question: Given a strongly connected and directed graph $G = (V,E)$ with positive weights define $E(t)$ to be the group of edges whose weight is at most $t$. Find an algorithm that calculates the minimal $t$ such that $G(t) = (V,E(t))$ is strongly connected.

I thought about running Dijkstra $v$ times from every vertex and then all of the edges will be the minimal $t$ but I am not sure the time complexity is the best. Is there a better solution for this problem?

$\endgroup$
  • $\begingroup$ What's the running time of the best algorithm you have so far? $\endgroup$ – D.W. Jan 24 at 15:55
  • $\begingroup$ The time complexity I got is O(E^2 + VE) $\endgroup$ – Daniel16 Jan 24 at 16:08
  • $\begingroup$ I heard about max flow min cut. $\endgroup$ – Daniel16 Jan 24 at 17:50
1
$\begingroup$

We can solve the problem in $\mathcal{O}(E \log V)$ by binary search.

We can identify the strongly connected components in a graph in linear ($\mathcal{O}(V + E)$) time. Thus we can check if the graph is strongly connected in linear time.

If $G(t_{0}) = (V, E(t_{0}))$ is strongly connected, so is $G(t) = (V, E(t))$ for $t \geq t_{0}$. Further, if $G(t_{0})$ is strongly connected, so is $G(t)$ where $t$ is the maximum edge weight that is at most $t_{0}$. Thus we can binary search for $t$ over all edge weights.

The algorithm is:

  1. Sort edges by weight. Let $w_{i}$ be the $i$th smallest edge weight (1-indexed). Set $w_{0} = -1$.
  2. Initialise binary search: set $l = 1$ and $h = |E| + 1$
  3. While $l \neq h$:
    • set $m = \lfloor\frac{l + h}{2}\rfloor$. Then, If $G(w_{m})$ is connected, set $h = m$. Otherwise set $l = m + 1$.
  4. If $l = |E| + 1$, no $t$ works. Otherwise, answer $t = w_{l}$

In the binary search, we maintain the invariant that $G(w_{h})$ is strongly connected (or $h = |E| + 1$), while $G(w_{l - 1})$ is not (assuming $|V| \geq 2$). We exit the loop when $l = h$, thus either $l = |E| + 1$ and the graph is not strongly connected for any $t$, or $G(w_{l})$ is strongly connected, but $G(w_{l-1})$ is not, thus $G(t)$ is not strongly connected for $t < w_{l}$. Thus the algorithm is correct.

The first step takes $\mathcal{O}(E \log E)$ time. The third step takes linear time and is executed at most $\log E$ times. Thus, the complexity is $\mathcal{O}((V + E) \log E) = \mathcal{O}(E \log V)$.

| cite | improve this answer | |
$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.