Survival algorithm for Network deterministic failures

Consider an undirected network $G = (V,E)$ in which edge $e$ $\in$ $E$ fails after (deterministic) time $t(e) > 0$. Network failure occurs at the first instant in which $G$ is no longer connected. Let $m = |E|$ and assume the values $\{t(e): e \in E\}$ are distinct.

You wish to determine the instant $\tau$ at which the network fails.

1- Suppose you solve this problem via an intuitive algorithm in which you first sort the edges according to $t(e)$ and then remove the edges, one at a time, to determine if the network has failed. Establish the complexity of this algorithm.

My Answer: We can sort edges in $O(m\log n)$ time + removing edges takes $O(1)$ * the number of edges to be removed $O(m)$. So the complexity is $O(m^2)$.

2- Show that a variation of your intuitive algorithm from part a can determine $\tau$ in a reduced time complexity in which a factor of m is changed to log m.

My expectation: I think we might use a heap for storing edges but I am not sure how to implement it.

3- Using what you know about spanning trees, can you write a new algorithm to im­prove upon (or equal) the complexity of your algorithm from part b? (Hint: The network will be failed as soon as every spanning tree. contains a failed edge.)

My expectation: I believe we need to find all spanning trees but I am not sure if this will help reduce complexity.

Can anyone help me solving the given problem or direct me towards a reasonable solution?

Part b

Suppose $t(e_1)>t(e_2)>\cdots$, what you want is $e_i$ such that the graph with $e_1,\ldots,e_i$ is connected. Part a checks the graph with $e_1,\ldots,e_m$, then the graph with $e_1,\ldots,e_{m-1}$, and so on. This process can be improved by binary search, i.e. checking the graph with $e_1,\ldots,e_{m/2}$, then graph with $e_1,\ldots,e_{m/4}$ or with $e_1,\ldots,e_{3m/4}$ depending on the result of the first check, and so on.

Part c

You don't need to check all spanning trees. You only need to find the spanning tree of whose edges the earliest failure time is maximized. This is known as a minimum bottleneck spanning tree (cost of an edge is the negative of its failure time).

• So, do you agree with me on the complexity of O(m^2) in part a ? .. that is what I am thinking about in part b but does the complexity drops to O(m log m)? – Bassem Apr 1 '18 at 12:57
• Yes, part a is $O(m^2)$. Binary search takes only $O(\log m)$ steps while each step costs $O(m)$. – xskxzr Apr 1 '18 at 13:37
• But, when we apply the binary search .. do we find the first instance $\tau$ in $O (m log m)$ because I believe we narrow the search but need when identifying $e_1,\ldots,e_{m/2}$ -for example- to search each arc that causes the first network disconnection .. am I right ? or my interpretation of the algorithm is wrong – Bassem Apr 1 '18 at 17:27
• You needn't search the edge causing the network disconnected. You only check whether the graph with $e_1,\ldots,e_{m/2}$ is connected. If yes, then check $e_1,\ldots,e_{m/4}$; if no, then check $e_1,\ldots,e_{3m/4}$, and so on. – xskxzr Apr 1 '18 at 17:37
• Oh .. I got it .. last question about part (c) .. I checked the minimum bottleneck spanning tree and found that it takes $O(m)$ time .. is that will be the complexity of the algorithm where I find minimum bottleneck spanning tree and pick the edge with the earliest failure time. or is there something more to be included ? – Bassem Apr 1 '18 at 18:05