Matroid Intersection under Minimum Rank Oracle
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866914219259068416 |
|---|---|
| author | Bárász, Mihály Bérczi, Kristóf Király, Tamás Oki, Taihei Yamaguchi, Yutaro Yokoi, Yu |
| author_facet | Bárász, Mihály Bérczi, Kristóf Király, Tamás Oki, Taihei Yamaguchi, Yutaro Yokoi, Yu |
| contents | In this paper, we consider the tractability of the matroid intersection problem under the minimum rank oracle. In this model, we are given an oracle that takes as its input a set of elements and returns as its output the minimum of the ranks of the given set in the two matroids. For the unweighted matroid intersection problem, we show how to construct a necessary part of the exchangeability graph, which enables us to emulate the standard augmenting path algorithm. For the weighted problem, the tractability is open in general. Nevertheless, we describe several special cases where tractability can be achieved, and we discuss potential approaches and the challenges encountered.
On the positive side, we present a solution for the case where no circuit of one matroid is contained within a circuit of the other. Additionally, we propose a fixed-parameter tractable algorithm, parameterized by the maximum size of a circuit of one matroid. We also show that a lexicographically maximal common independent set can be found by the same approach, which leads to a nontrivial approximation ratio for finding a maximum-weight common independent set. On the negative side, we prove that the approach employed for the tractable cases above involves an NP-hard problem in the general case. We also show that if we consider the generalization to polymatroid intersection, even the unweighted problem is hard under the minimum rank oracle. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2407_03229 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Matroid Intersection under Minimum Rank Oracle Bárász, Mihály Bérczi, Kristóf Király, Tamás Oki, Taihei Yamaguchi, Yutaro Yokoi, Yu Data Structures and Algorithms Combinatorics In this paper, we consider the tractability of the matroid intersection problem under the minimum rank oracle. In this model, we are given an oracle that takes as its input a set of elements and returns as its output the minimum of the ranks of the given set in the two matroids. For the unweighted matroid intersection problem, we show how to construct a necessary part of the exchangeability graph, which enables us to emulate the standard augmenting path algorithm. For the weighted problem, the tractability is open in general. Nevertheless, we describe several special cases where tractability can be achieved, and we discuss potential approaches and the challenges encountered. On the positive side, we present a solution for the case where no circuit of one matroid is contained within a circuit of the other. Additionally, we propose a fixed-parameter tractable algorithm, parameterized by the maximum size of a circuit of one matroid. We also show that a lexicographically maximal common independent set can be found by the same approach, which leads to a nontrivial approximation ratio for finding a maximum-weight common independent set. On the negative side, we prove that the approach employed for the tractable cases above involves an NP-hard problem in the general case. We also show that if we consider the generalization to polymatroid intersection, even the unweighted problem is hard under the minimum rank oracle. |
| title | Matroid Intersection under Minimum Rank Oracle |
| topic | Data Structures and Algorithms Combinatorics |
| url | https://arxiv.org/abs/2407.03229 |