On the Complexity of Some Enumeration Problems for Matroids

Abstract

Let M be a matroid defined by an independence oracle on ground set S, and let $A\subseteq 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.