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.
@article{10_37236_12773,
author = {Bernd G\"artner and Simon Weber and Joel Widmer},
title = {Realizability in {Matou\v{s}ek} unique sink orientations: characterization and complexity gap},
journal = {The electronic journal of combinatorics},
year = {2025},
volume = {32},
number = {2},
doi = {10.37236/12773},
zbl = {1565.68173},
url = {http://geodesic.mathdoc.fr/articles/10.37236/12773/}
}
TY - JOUR
AU - Bernd Gärtner
AU - Simon Weber
AU - Joel Widmer
TI - Realizability in Matoušek unique sink orientations: characterization and complexity gap
JO - The electronic journal of combinatorics
PY - 2025
VL - 32
IS - 2
UR - http://geodesic.mathdoc.fr/articles/10.37236/12773/
DO - 10.37236/12773
ID - 10_37236_12773
ER -
%0 Journal Article
%A Bernd Gärtner
%A Simon Weber
%A Joel Widmer
%T Realizability in Matoušek unique sink orientations: characterization and complexity gap
%J The electronic journal of combinatorics
%D 2025
%V 32
%N 2
%U http://geodesic.mathdoc.fr/articles/10.37236/12773/
%R 10.37236/12773
%F 10_37236_12773
Bernd Gärtner; Simon Weber; Joel Widmer. Realizability in Matoušek unique sink orientations: characterization and complexity gap. The electronic journal of combinatorics, Tome 32 (2025) no. 2. doi: 10.37236/12773
