Sparse connectivity certificates via MA orderings in graphs

For an undirected multigraph G=(V,E), let α be a positive integer weight function on V. For a positive integer k, G is called (k,α)-connected if any two vertices u,v∈V remain connected after removal of any pair (Z,E^′) of a vertex subset Z⊆V-{u,v} and an edge subset E^′⊆E such that ∑_v∈Zα(v)+|E^′|<k. The (k,α)-connectivity is an extension of several common generalizations of edge-connectivity and vertex-connectivity. Given a (k,α)-connected graph G, we show that a (k,α)-connected spanning subgraph of G with O(k|V|) edges can be found in linear time by using MA orderings. We also show that properties on removal cycles and preservation of minimum cuts can be extended in the (k,α)-connectivity.