Greedily generating all bases of a matroid by base exchanges

A classical result states that one can generate a spanning tree by repeatedly adding edges such that no cycle is created. More generally, one can compute a base of a matroid in a similar greedy way. We show that one can not only compute one base of a matroid greedily but exhaustively generate them all by a simple base-exchange greedy algorithm. For example, the spanning trees of a graph can be generated by edge exchanges using the following greedy rule: Minimize the larger label of an edge that enters or exits the current spanning tree and which creates a new spanning tree (i.e., that hasn’t been visited already). Amazingly, this works for any graph, for any labeling of its edges, for any initial spanning tree, and regardless of how you choose the edge with the smaller label in each exchange.

In general, for any matroid, we can greedily compute a listing of all its bases matroid such that consecutive bases differ by base exchanges. Furthermore, we can generate these orders using “history-free” iterative algorithms. More specifically, if m is the number of elements in the matroid, we store O(m) bits of data and use O(m) time per base assuming O(1) time independence and coindependence oracles.

During the talk, we will not assume any previous knowledge of matroids and mainly focus on the particular case of spanning trees of graphs.

This is joint work with Torsten Mütze and Aaron Williams.