On Degeneracy in the P-Matroid Oriented Matroid Complementarity Problem
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2023
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866911967705300992 |
|---|---|
| author | Borzechowski, Michaela Weber, Simon |
| author_facet | Borzechowski, Michaela Weber, Simon |
| contents | Klaus showed that the Oriented Matroid Complementarity Problem (OMCP) can be solved by a reduction to the problem of sink-finding in a unique sink orientation (USO) if the input is promised to be given by a non-degenerate extension of a P-matroid. In this paper, we investigate the effect of degeneracy on this reduction. On the one hand, this understanding of degeneracies allows us to prove a linear lower bound on the number of vertex evaluations required for sink-finding in P-matroid USOs, the set of USOs obtainable through Klaus' reduction. On the other hand, it allows us to adjust Klaus' reduction to also work with degenerate instances. Furthermore, we introduce a total search version of the P-Matroid Oriented Matroid Complementarity Problem (P-OMCP). Given any extension of any oriented matroid M, by reduction to a total search version of USO sink-finding we can either solve the OMCP, or provide a polynomial-time verifiable certificate that M is not a P-matroid. This places the total search version of the P-OMCP in the complexity class Unique End of Potential Line (UEOPL). |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2302_14585 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | On Degeneracy in the P-Matroid Oriented Matroid Complementarity Problem Borzechowski, Michaela Weber, Simon Combinatorics Computational Complexity Klaus showed that the Oriented Matroid Complementarity Problem (OMCP) can be solved by a reduction to the problem of sink-finding in a unique sink orientation (USO) if the input is promised to be given by a non-degenerate extension of a P-matroid. In this paper, we investigate the effect of degeneracy on this reduction. On the one hand, this understanding of degeneracies allows us to prove a linear lower bound on the number of vertex evaluations required for sink-finding in P-matroid USOs, the set of USOs obtainable through Klaus' reduction. On the other hand, it allows us to adjust Klaus' reduction to also work with degenerate instances. Furthermore, we introduce a total search version of the P-Matroid Oriented Matroid Complementarity Problem (P-OMCP). Given any extension of any oriented matroid M, by reduction to a total search version of USO sink-finding we can either solve the OMCP, or provide a polynomial-time verifiable certificate that M is not a P-matroid. This places the total search version of the P-OMCP in the complexity class Unique End of Potential Line (UEOPL). |
| title | On Degeneracy in the P-Matroid Oriented Matroid Complementarity Problem |
| topic | Combinatorics Computational Complexity |
| url | https://arxiv.org/abs/2302.14585 |