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: 2-edge-connectivity, 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 linear-time algorithms for finding a minimal 2-edge-connected 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 CCR89-10707.
E-mail addresses for the authors: kelsen@cs.utexas.edu (Pierre Kelsen) and vlr@cs.utexas.edu (Vijaya Ramachandran).