Realizability in Matoušek Unique Sink Orientations: Characterization and Complexity Gap

Abstract

Various algebraic and geometric problems reduce to the sink-finding problem in unique sink orientations (USOs), which are orientations of the hypercube graph that have a unique sink in every subcube. A USO is called realizable if it can arise from applying one of these reductions. We study how realizability influences the query complexity of the sink-finding problem. To this end, we consider a specific subclass of USOs, the so-called Matoušek USOs. The Matoušek USOs are a family of USOs which are a translation of the LP-type problems used by Matoušek to show that the Sharir-Welzl algorithm for LP-type problems may require at least subexponential time [Matoušek, 1994]. Gärtner showed that the Random Facet algorithm for USO sink-finding requires at least subexponentially many vertex evaluation queries on Matoušek USOs, but at most quadratically many queries on realizable Matoušek USOs [Gärtner, 2002]. However, Gärtner did not fully characterize this realizable subset. In this paper, we fully characterize the realizable subset of the Matoušek-type USOs (the USOs isomorphic to a Matoušek USO) and also provide concrete realizations using instances of the P-Matrix Linear Complementarity Problem, basing our work on the so-called cyclic-P-matroids studied by Fukuda, Klaus, and Miyata. We further extend the results of Matoušek and Gärtner for the Random Facet algorithm to the query complexity of the sink-finding problem itself: we show that sink-finding is strictly easier on realizable Matoušek-type USOs than on all Matoušek-type USOs. We show that in the realizable case $O(\log^2 n)$ queries suffice, while in general exactly n queries are needed.