# Finding minimal strongly connected graph

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?

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

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)$$.