On the complexity of some enumeration problems for matroids

Let M be a matroid defined by an independence oracle on ground set S, and let A subset of S. We present an incremental polynomial-time algorithm for enumerating all minimal ( maximal) subsets of S which span (do not span) A. Special cases of these problems include the generation of bases, circuits, hyperplanes, flats of given rank, circuits through a given element, generalized Steiner trees, and multiway cuts in graphs, as well as some other applications. We also consider some tractable and NP-hard generation problems related to systems of polymatroid inequalities and (generalized) packing and spanning in matroids.