Enumeration of Bases in Matroid with Exponentially Large Ground Set
Abstract
When we deal with a matroid ${\mathcal M}=(U,{\mathcal I})$, we usually assume that it is implicitly given by means of the membership (MEM) oracle. Many existing efficient algorithms run in polynomial time with respect to $|U|$ and the running time of the MEM-oracle. However, they are not efficient any more when $U$ is exponentially large in some context. In this paper, we study two problems of enumerating bases in such matroids. First, we present an incremental-polynomial algorithm that enumerates all minimum-weighted bases, where the bounding polynomial does not depend on $|U|$. To design the algorithm, we assume two oracles other than the MEM-oracle: the MinB-oracle that returns a minimum basis and the REL-oracle that returns a relevant element one by one in non-decreasing order of weight. The proposed algorithm is applicable to enumeration of minimum bases of binary matroids from cycle space, path space and cut space, all of which have exponentially large $U$ with respect to a given graph. The highlight in this context is that, to design the REL-oracle for cut space, we develop the first polynomial-delay algorithm that enumerates all relevant cuts of a given graph in non-decreasing order of weight. Finally, we present a polynomial-delay algorithm that enumerates all sets of linearly independent $r$-dimensional $r$ vectors over $\mathit{GF}(2)$. Using the algorithm, we can enumerate all unweighted bases of a binary matroid such that elements are closed under addition, in polynomial-delay with respect to the matroid rank $r$.