A 2-Level Cactus-Tree Model for Minimum and Minimum+1 Edge-Cuts in a Graph and its Incremental Maintenance

One of measures of network reliability is the size and location of its "bottlenecks".
A network is usually represented by a multigraph, and its bottlenecks by the
minimum and "near" minimum cuts of this multigraph.

The known cactus-tree model of Dinitz, Karzanov, and Lomonosov, represents in a clear and compact
way all the minimum cuts of a graph. It is used for network design and for dynamic graph algorithms.

Let k denote the cardinality of a minimum edge cut of a graph.
We generalize the cactus-tree model to represent all the k- and (k+1)-cuts (i.e., the minimum and the minimum+1 cuts).
Our representations have properties similar to those of the cactus-tree model, although they are different for k odd and even.
In our models, the structure of k- and (k+1)-cuts is almost as simple as the structure of
1- and 2-cuts for k odd, and of 2- and 3-cuts for k even.

Using our structures, we give efficient algorithms for the following problem.
Assume that the graph undergoes insertions of edges.
At any time the algorithm determines, for a given pair of vertices $x,y$,
whether there are at least k+2 edge disjoint paths between them.
The complexity of these algorithms, for k odd and even, is the same as
previously achieved for the cases k=1 and k=2, respectively.

To derive our results, we use new tools for modeling connectivity structures, among them
a simple characterization of families of cuts that can be modeled by a cactus-tree type graph.


Joint work with Yefim Dinitz