On degeneracy in the P-matroid oriented matroid complementarity problem

Abstract

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 Pmatroid 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).