In this chapter, we discuss how to decompose a given multigraph G into a set of forests to obtain a spanning subgraph that preserves the edge/vertex-connectivity of G. We introduce a total ordering of the vertices in a multigraph G, called a maximum adjacency (MA) ordering, and then find such a forest decomposition. Based on this set of forests, we can convert G into a sparse graph in linear time while preserving the edge/vertex-connectivity. This sparsification technique can be used for many connectivity algorithms as a preprocessing that reduces the size of input graphs. We describe some of the applications of connectivity algorithms.

Spanning Subgraphs Preserving Connectivity

A k-edge-connectivity certificate (resp. k-vertex-connectivity certificate) of a multigraph G is a spanning subgraph H of G such that, for any two vertices u, ν and any positive integer k′ ≤ k, there are k′ edge-disjoint (resp. internally vertex-disjoint) paths between u and ν in H if and only if there are k edgedisjoint (resp. internally vertex-disjoint) paths between u and ν in G. That is, a kedge- connectivity (resp. k-vertex-connectivity) certificate is defined as a spanning subgraph that preserves the edge-connectivity (resp. vertex-connectivity) up to k. Therefore,when H is a k-edge-connectivity certificate (resp. k-vertex-connectivity certificate) of G, H is k-edge-connected (resp. k-vertex-connected) if and only if G is k-edge-connected (resp. k-vertex-connected). If a k-edge-connectivity certificate H of G is k-edge-connected, then |ε(H)| ≥ holds since the degree of any vertex in H is at least k. Then we say that a k-edge-connectivity certificate H is sparse if |ε(H)| = O(kn). A sparse k-vertex-connectivity certificate is similarly defined. It is known that such a certificate exists [203].