Enumeration of Bases in Matroid with Exponentially Large Ground Set
Yuki Nishimura, Kazuya Haraguchi · 2025
Read Enumeration of Bases in Matroid with Exponentially Large Ground Set by Yuki Nishimura, Kazuya Haraguchi (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2504-11728.txt.
Introduction
Yuki Nishimura and Kazuya Haraguchi tackle a listing task in a 2025 math paper. Their objects, called matroids, model free sets in graphs and vector sets alike. Most tools assume the ground set can be held in view, but some tasks make that set grow beyond any list a machine could store.
The pair give two methods to list the maximal free sets, called bases, whose run time does not rest on the ground set's size. One lists the lightest bases first in steady steps, with the rest at even pace. Two extra helper tools feed each method. The work opens huge matroids to full listing.
Catalog record
| CREATOR | Yuki Nishimura, Kazuya Haraguchi |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 92 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2504-11728
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Enumeration of Bases in Matroid with Exponentially Large Ground Set Thanks: The work is partially supported by JSPS KAKENHI Grant Number 25K14993. Yuki Nishimura, Kazuya Haraguchi Abstract When we deal with a matroid ℳ = ( U , ℐ ) {\mathcal{M}}=(U,{\mathcal{I}}) , we usually assume that it is implicitly given by means of the independence (IND) oracle. Time complexity of many existing algorithms is polynomially bounded with respect to | U | |U| and the running time of the IND-oracle. However, they are not efficient any more when U U is exponentially large in some context. In this paper, we propose two algorithms for enumerating matroid bases such that the time complexity does not depend on | U | |U| . For some integer L L , the first algorithm enumerates the first L L minimum-weight bases in incremental-polynomial time and the remaining ones in polynomial-delay. To design the algorithm, we assume two oracles other than the IND-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 and cut space, all of which have exponentially large U 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. The second algorithm enumerates all sets of linearly independent r r -dimensional r r vectors over 𝐺𝐹 ( 2 ) \mathit{GF}(2) in polynomial-delay, which immediately yields a polynomial-delay algorithm that enumerates all unweighted bases of a binary matroid such that elements are closed under addition. 1 Introduction Let \real,\real_{\geq 0},\real_{+} denote the sets of reals, nonnegative reals and positive reals, respectively. For a ground set U and a family {\mathcal{I}} of subsets of U , {\mathcal{M}}=(U,{\mathcal{I}}) is called a matroid if the following axioms are satisfied. (I) \emptyset\in{\mathcal{I}} ; (II) for I,J\subseteq U such that I\subseteq J , J\in{\mathcal{I}} implies I\in{\mathcal{I}} ; and (III) for I,J\in{\mathcal{I}} , if |I|<|J| , then there is x\in J-I such that I\cup\{x\}\in{\mathcal{I}} . A subset I\in{\mathcal{I}} (resp., I\not\in{\mathcal{I}} ) is called independent (resp., dependent ), and a maximal independent set is called a basis . It is well-known that the cardinality of any basis is equal and called the rank of \mathcal{M} . Given a weight function w:U\to\real , we write w(S)\coloneqq\sum_{x\in S}w(x) for S\subseteq U and call it the weight of S . A basis is minimum-weight (or minimum for short) if the weight attains the minimum over all bases. Introduced by Whitney [ 43 ] , matroid is among well-studied discrete structures in theoretical computer science. Various combinatorial problems on matroid can be solved efficiently (e.g., minimum-weight basis [ 11 ] , matroid intersection [ 8 , 12 ] , matroid partition [ 8 ] ). It is so expressive a mathematical model that admits us to solve many real problems (e.g., minimum spanning tree). A matroid {\mathcal{M}}=(U,{\mathcal{I}}) is usually given by means of independence oracle (a.k.a., membership oracle) that returns whether S\in{\mathcal{I}} or S\not\in{\mathcal{I}} to a query subset S\subseteq U . Enumeration problem in general asks to list all required solutions without duplication and has practical applications in such fields as data mining and bioinformatics [ 1 , 13 , 27 , 42 ] . In general, an enumeration algorithm takes at least the computation time proportional to the output size, where the output size can be exponentially large with respect to the input size. An enumeration algorithm has been evaluated in terms of both input size and output size. According to [ 21 ] , the algorithm is called • output-polynomial if the overall computation time is bounded by a polynomial with respect to the input size and output size; • incremental-polynomial ( incremental-poly ) if the computation time for finding the \ell -th solution is bounded by a polynomial with respect to the input size and \ell ; and • polynomial-delay ( poly-delay ) if the delay (i.e., computation time between any two consecutive outputs) is bounded by a polynomial with respect to the input size. Various enumeration problems have been studied in the context of matroid [ 23 , 25 , 31 ] . Uno [ 39 ] proposed efficient algorithms for enumerating all bases for such fundamental matroids as graphic matroid, linear matroid and matching matroid. For graphic matroid, there is also an algorithm for enumerating all bases (i.e., spanning trees) [ 36 ] , which is optimal in the sense of both time and space. Hamacher et al. [ 17 ] presented an algorithm to enumerate k -smallest bases in the sense of weight in {\mathcal{O}}(|U|\log|U|+k\cdot|U|\cdot r\cdot\tau_{\mathrm{IND}}) time, where \tau_{\mathrm{IND}} denotes the computation time of the independence oracle. These algorithms are efficient in the sense that the time complexity is polynomially bounded. The bounding polynomials depend on the cardinality |U| of the ground set U . In the literature, however, there are matroids such that the ground set consists of an exponential number of elements with respect to the size of a given graph; e.g., binary matroids from cycle space [ 9 , 3 ] , path space [ 18 ] , cut space [ 9 ] and U(T) -space [ 19 ] . These matroids are never just artificial. For example, a basis in the binary matroid from cycle space, called a minimum cycle basis in the literature, has applications in electric engineering [ 4 ] , structural analysis of skeletal structures [ 7 ] , network analysis [ 40 ] and periodic event scheduling [ 5 ] . A minimum cycle basis can be found in polynomial time [ 20 , 32 , 35 ] , and there are problems of finding other kinds of cycle basis [ 22 ] . However, we cannot expect the above-mentioned enumeration algorithms to run efficiently for matroids like this. In this paper, assuming a matroid with an exponentially large ground set, we propose two new enumeration algorithms, one for all minimum-weight bases and the other for all (unweighted) bases, respectively. The point is that, for both algorithms, the polynomials bounding the time complexity do not depend on the ground set size. After we prepare terminologies, notations and fundamental properties in Sect. 2 , we present the main contributions of the paper from Sections 3 to 5 , followed by concluding remarks in Sect. 6 . Enumeration of Minimum Bases (Sect. 3 ). To design the algorithm for this purpose, we assume two oracles other than the independence oracle: the minimum basis oracle that returns a minimum basis and the relevant oracle that returns a “relevant” element one by one in non-decreasing order of weight. An element is relevant if there is a minimum basis that contains it. For some integer L , the proposed algorithm generates the \ell -th solution (\ell\leq L) in incremental-poly time with respect to the running times of the three oracles and the matroid rank, and the remaining solutions are enumerated in O(r) delay (i.e., poly-delay). Application to Binary Matroids (Sect. 4 ). We