An Algorithm for Packing Connectors

Given an undirected graphG=(V, E) and a partition {S, T} ofV, anS−Tconnectoris a set of edgesF⊆Esuch that every component of the subgraph (V, F) intersects bothSandT. If eitherSorTis a singleton, then anS−Tconnector is a spanning subgraph ofG. On the other hand, ifGis bipartite with colour classesSandT, then anS−Tconnector is an edge cover ofG(a set of edges covering all vertices). AnS−Tconnector is a common spanning set of two graphic matroids onE. We prove a theorem on packing common spanning sets of certain matroids, generalizing a result of Davies and McDiarmid on strongly base orderable matroids. As a corollary, we obtain anO(τ(n, m)+nm) time algorithm for finding a maximum number ofS−Tconnectors, whereτ(n, m) denotes the complexity of finding a maximum number of edge disjoint spanning trees in a graph onnvertices andmedges. Since the best known bound forτ(n, m) isO(nm log(m/n)), this bound for packingS−Tconnectors is as good as the current bound for packing spanning trees.