Enumeration of Bases in Matroid with Exponentially Large Ground Set
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916946905137152 |
|---|---|
| author | Nishimura, Yuki Haraguchi, Kazuya |
| author_facet | Nishimura, Yuki Haraguchi, Kazuya |
| contents | When we deal with a matroid ${\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|$ and the running time of the IND-oracle. However, they are not efficient any more when $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|$. For some integer $L$, the first algorithm enumerates the first $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$ 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$-dimensional $r$ vectors over $\mathit{GF}(2)$ in polynomial-delay, which immediately yields a polynomial-delay algorithm %%with respect to the matroid rank $r$ that enumerates all unweighted bases of a binary matroid such that elements are closed under addition. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2504_11728 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Enumeration of Bases in Matroid with Exponentially Large Ground Set Nishimura, Yuki Haraguchi, Kazuya Data Structures and Algorithms Discrete Mathematics G.2.2 When we deal with a matroid ${\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|$ and the running time of the IND-oracle. However, they are not efficient any more when $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|$. For some integer $L$, the first algorithm enumerates the first $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$ 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$-dimensional $r$ vectors over $\mathit{GF}(2)$ in polynomial-delay, which immediately yields a polynomial-delay algorithm %%with respect to the matroid rank $r$ that enumerates all unweighted bases of a binary matroid such that elements are closed under addition. |
| title | Enumeration of Bases in Matroid with Exponentially Large Ground Set |
| topic | Data Structures and Algorithms Discrete Mathematics G.2.2 |
| url | https://arxiv.org/abs/2504.11728 |