I am trying to solve below question from tardos. Any suggestions or help would be appreciated.
You’ve been called in to help some network administrators diagnose the extent of a failure in their network. The network is designed to carry traffic from a designated source node s to a designated target node t, so we will model it as a directed graph G = (V,E), in which the capacity of each edge is 1, and in which each node lies on at least one path from s to t.
Now, when everything is running smoothly in the network, the maximum s-t flow in G has value k. However, the current situation - and the reason you’re here - is that an attacker has destroyed some of the edges in the network, so that there is now no path from s to t using the remaining (surviving) edges. For reasons that we won’t go into here, they believe the attacker has destroyed only k edges, the minimum number needed to separate s from t (i.e. the size of a minimum s-t cut); and we’ll assume they’re correct in believing this. The network administrators are running a monitoring pool on node s, which has the following behavior: if you issue the command ping(v), for a given node v, it will tell you whether there is currently a path from s to v. (So pint(t) reports that no path currently exists; on the other hand, ping(s) always reports a path from s to itself.) Since it’s not practical to go out and inspect every edge of the network, they’d like to determine the extent of the failure using this monitoring tool, through judicious use of the ping command. So here’s the problem you face: give an algorithm that issues a sequence of ping commands to various nodes in the network, and then reports the full set of nodes that are not currently reachable from s. You could do this by pinging every node in the network, of course, but you’d like to do it using many fewer pings (given the assumption that only k edges have been deleted). In issuing this sequence, your algorithm is allowed to decide which node to ping next based on the outcome of earlier ping operations. Give an algorithm that accomplishes this task using only O(k log n) pings.
Use Floyd-Fulkerson on the complete network to calculate a max flow, which will consist of k edge-disjoint paths.
Since exactly k edges have been deleted, and all flow is cut off, exactly one edge must have been deleted along each of these paths.
For each path, which will contain at most n edges, do a binary search to discover the position of the broken edge, using O(log n) pings to the nodes on the path.