The general structure of edge-connectivity of a vertex subset in a graph and its incremental maintenance. Odd case

Let G = (V, E) be an undirected graph, S be a subset of its vertices, C-S b e the set of minimum edge-cuts partitioning S, and S be the cardinality of such a cut. We suggest a graph structure, called the connectivity carcass o f S, that represents both cuts in CS and the partition of V by all these cu ts; its size is O(min{\E\, lambda(S)\V\}). In this paper we present general constructions and study in detail the case lambda(S) odd; the specifics of the case S even are considered elsewhere. For an adequate description of t he connectivity carcass we introduce a new type of graph: locally orientabl e graphs, which generalize digraphs. The connectivity carcass consists of a locally orientable quotient graph of G, a cactus tree (in case S odd, just a tree) representing all distinct partitions of S by cuts in C-S, and a ma pping connecting them. One can build it in O (\S\) max-flow computations in G. For an arbitrary sequence of u edge insertions not changing lambda(S), the connectivity carcass can be maintained in time O (\V\ min {\E\, lambda( S) \V\} + u). For two vertices of G, queries asking whether they are separa ted by a cut in C-S are answered in O(1) worst-case time per query. Another possibility is to maintain the carcass in O (\S\ min {\E\, lambda(S) \V\} + u) time, but to answer the queries in O(1) time only if at least one of t he vertices belongs to S.