License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FUN.2022.22
URN: urn:nbn:de:0030-drops-159928
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/15992/
Merino, Arturo ;
Mütze, Torsten ;
Williams, Aaron
All Your bases Are Belong to Us: Listing All Bases of a Matroid by Greedy Exchanges
Abstract
You provide us with a matroid and an initial base. We say that a subset of the bases "belongs to us" if we can visit each one via a sequence of base exchanges starting from the initial base. It is well-known that "All your base are belong to us". We refine this classic result by showing that it can be done by a simple 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 spanning tree that is new (i.e., 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. Furthermore, by maintaining a small amount of information, we can generate each successive spanning tree without storing the previous trees.
In general, for any matroid, we can greedily compute a listing of all its bases matroid such that consecutive bases differ by a base exchange. Our base exchange Gray codes apply a prefix-exchange on a prefix-minor of the matroid, and we can generate these orders using "history-free" iterative algorithms. More specifically, we store O(m) bits of data, and use O(m) time per base assuming O(1) time independence and coindependence oracles.
Our work generalizes and extends a number of previous results. For example, the bases of the uniform matroid are combinations, and they belong to us using homogeneous transpositions via an Eades-McKay style order. Similarly, the spanning trees of fan graphs belong to us via face pivot Gray codes, which extends recent results of Cameron, Grubb, and Sawada [Pivot Gray Codes for the Spanning Trees of a Graph ft. the Fan, COCOON 2021].
BibTeX - Entry
@InProceedings{merino_et_al:LIPIcs.FUN.2022.22,
author = {Merino, Arturo and M\"{u}tze, Torsten and Williams, Aaron},
title = {{All Your bases Are Belong to Us: Listing All Bases of a Matroid by Greedy Exchanges}},
booktitle = {11th International Conference on Fun with Algorithms (FUN 2022)},
pages = {22:1--22:28},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-232-7},
ISSN = {1868-8969},
year = {2022},
volume = {226},
editor = {Fraigniaud, Pierre and Uno, Yushi},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/15992},
URN = {urn:nbn:de:0030-drops-159928},
doi = {10.4230/LIPIcs.FUN.2022.22},
annote = {Keywords: Matroids, base exchange, Gray codes, combinatorial generation, greedy algorithms, spanning trees}
}
