Surender Baswana is a faculty member at IIT Kanpur. Prior to joining IIT Kanpur, he was a Postdoctoral researcher at MPII (2003-06). Currently, he is a visiting scientist at Heinz Nixdorf Institute Paderborn, on sabbatical leave from IIT Kanpur. His research at Heinz Nixdorf Institute is supported by Alexander von Humboldt Fellowship for experienced researchers. His research interest lies in efficient algorithms for dynamic graphs.

AG 1   Info

AG Audience

English

45 Minutes

Saarbrücken

Let G=(V,E) be an undirected graph on n vertices with nonnegative capacities on its edges. The mincut sensitivity problem for insertion of an edge is defined as follows. Build a compact data structure for G and a given set Q of pairs of vertices that, on receiving any edge (x,y) of positive capacity as query input, can efficiently report the set of all pairs from Q whose mincut value gets increased upon insertion of edge (x,y) to G. The only result that exists for this problem is for a single pair of vertices [Picard and Queyranne, Mathematical Programming Study, 1980]. We present the following results for the single source and all-pairs version of this problem.

Single source: Given any designated source vertex s, there exists an O(n) size data structure that can output the set of all the vertices whose mincut value to s gets increased upon insertion of any query edge. The time guaranteed to answer any query is O(n). We also show that this result is in stark contrast with directed graphs -- any data structure for single source mincut sensitivity for insertion of an edge will need at least n^2 bits of space in the worst case for at least one directed graph on n vertices.

All-pairs: There exists an O(n^2) size data structure that can output the set of all-pairs of vertices whose mincut value gets increased upon insertion of any query edge.
The time guaranteed to answer any query is O(k), where k is the number of pairs of vertices whose mincut increases.

To derive our results, we use interesting insights into the nearest and the farthest mincuts for a pair of vertices. In addition, a crucial result that we establish, and use in our data structures, is that there exists a directed acyclic graph of O(n) size that compactly stores farthest mincuts from all vertices to any designated vertex in the graph. We believe that this result is of independent interest, especially because it also complements a previously existing result by Hariharan et al. [STOC 2007] that the nearest mincuts from all vertices to any designated vertex is a laminar family, and hence can be stored compactly in a tree structure of O(n) size.

(This is a joint work with Till Knollmann and Shiv Gupta).

Sándor Kisfaludi-Bak

--email hidden

passcode not visible

logged in users only