
The Complexity of Finding Minimal Spanning Subgraphs ?
Pierre Kelsen?
Vijaya Ramachandran?
Department of Computer Sciences
University of Texas, Austin, TX 78712
February 6, 1991
Abstract
Let P be a property of graphs (directed or undirected). We consider the following problem: given a graph G that has property P , find a minimal spanning subgraph of G with property P . We describe an algorithm for this problem and prove that it is correct under some rather weak assumptions about P . We then analyze the number of iterations of this algorithm. By suitably restricting the graph properties, we devise a general technique to construct graphs for which the algorithm requires a large number of iterations.
We apply the above technique to three concrete graph properties: 2edgeconnectivity, biconnectivity, and strong connectivity. We obtain a tight lower bound of ?(log n) on the number of iterations of the algorithm for finding minimal spanning subgraphs with these properties; this resolves open questions posed earlier with regard to these properties. This also implies that the worst case sequential running time of the algorithm for these three properties is ?(m+n log n). We then give refinements of the basic algorithm that yield the first lineartime algorithms for finding a minimal 2edgeconnected and a minimal biconnected spanning subgraph of a graph. Finally, we provide evidence that the problem of refining the algorithm to find a minimal strongly connected spanning subgraph in linear time is more difficult.
o
?This work was supported in part by NSF grant CCR8910707.
Email addresses for the authors: kelsen@cs.utexas.edu (Pierre Kelsen) and vlr@cs.utexas.edu (Vijaya
Ramachandran).