Faster algorithms on linear delta-matroids
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866916130601304064 |
|---|---|
| author | Koana, Tomohiro Wahlström, Magnus |
| author_facet | Koana, Tomohiro Wahlström, Magnus |
| contents | We show new algorithms and constructions over linear delta-matroids. We observe an alternative representation for linear delta-matroids, as a contraction representation over a skew-symmetric matrix. This is equivalent to the more standard "twist representation" up to $O(n^ω)$-time transformations, but is much more convenient for algorithmic tasks. For instance, the problem of finding a max-weight feasible set now reduces directly to the problem of finding a max-weight basis in a linear matroid. Supported by this representation, we provide new algorithms and constructions over linear delta-matroids. We show that the union and delta-sum of linear delta-matroids define linear delta-matroids, and a representation for the resulting delta-matroid can be constructed in randomized time $O(n^ω)$. Previously, it was only known that these operations define delta-matroids. We also note that every projected linear delta-matroid can be represented as an elementary projection. This implies that several optimization problems over (projected) linear delta-matroids, including the coverage, delta-coverage, and parity problems, reduce (in their decision versions) to a single $O(n^ω)$-time matrix rank computation. Using the methods of Harvey, previously used by Cheung, Lao and Leung for linear matroid parity, we furthermore show how to solve the search versions in the same time. This improves on the $O(n^4)$-time augmenting path algorithm of Geelen, Iwata and Murota. Finally, we consider the maximum-cardinality delta-matroid intersection problem. Using Storjohann's algorithms for symbolic determinants, we show that such a solution can be found in $O(n^{ω+1})$ time. This is the first polynomial-time algorithm for the problem, solving an open question of Kakimura and Takamatsu. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2402_11596 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Faster algorithms on linear delta-matroids Koana, Tomohiro Wahlström, Magnus Data Structures and Algorithms Discrete Mathematics F.2.2 We show new algorithms and constructions over linear delta-matroids. We observe an alternative representation for linear delta-matroids, as a contraction representation over a skew-symmetric matrix. This is equivalent to the more standard "twist representation" up to $O(n^ω)$-time transformations, but is much more convenient for algorithmic tasks. For instance, the problem of finding a max-weight feasible set now reduces directly to the problem of finding a max-weight basis in a linear matroid. Supported by this representation, we provide new algorithms and constructions over linear delta-matroids. We show that the union and delta-sum of linear delta-matroids define linear delta-matroids, and a representation for the resulting delta-matroid can be constructed in randomized time $O(n^ω)$. Previously, it was only known that these operations define delta-matroids. We also note that every projected linear delta-matroid can be represented as an elementary projection. This implies that several optimization problems over (projected) linear delta-matroids, including the coverage, delta-coverage, and parity problems, reduce (in their decision versions) to a single $O(n^ω)$-time matrix rank computation. Using the methods of Harvey, previously used by Cheung, Lao and Leung for linear matroid parity, we furthermore show how to solve the search versions in the same time. This improves on the $O(n^4)$-time augmenting path algorithm of Geelen, Iwata and Murota. Finally, we consider the maximum-cardinality delta-matroid intersection problem. Using Storjohann's algorithms for symbolic determinants, we show that such a solution can be found in $O(n^{ω+1})$ time. This is the first polynomial-time algorithm for the problem, solving an open question of Kakimura and Takamatsu. |
| title | Faster algorithms on linear delta-matroids |
| topic | Data Structures and Algorithms Discrete Mathematics F.2.2 |
| url | https://arxiv.org/abs/2402.11596 |