Realizability in Matoušek Unique Sink Orientations: Characterization and Complexity Gap
METADATA ONLY
Loading...
Author / Producer
Date
2025
Publication Type
Journal Article
ETH Bibliography
yes
Citations
Altmetric
METADATA ONLY
Data
Rights / License
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 & scaron;ek USOs. The Matou & scaron;ek USOs are a family of USOs which are a translation of the LP-type problems used by Matou & scaron;ek to show that the Sharir-Welzl algorithm for LP-type problems may require at least subexponential time [Matou & scaron;ek, 1994]. G & auml;rtner showed that the Random Facet algorithm for USO sink-finding requires at least subexponentially many vertex evaluation queries on Matou & scaron;ek USOs, but at most quadratically many queries on realizable Matou & scaron;ek USOs [G & auml;rtner, 2002]. However, G & auml;rtner did not fully characterize this realizable subset. In this paper, we fully characterize the realizable subset of the Matou & scaron;ektype USOs (the USOs isomorphic to a Matou & scaron;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 & scaron;ek and G & auml;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 & scaron;ek-type USOs than on all Matou & scaron;ek-type USOs. We show that in the realizable case O(log2 n) queries suffice, while in general exactly n queries are needed.
Permanent link
Publication status
published
External links
Editor
Book title
Journal / series
Volume
32 (2)
Pages / Article No.
Publisher
Electronic Journal of Combinatorics
Event
Edition / version
Methods
Software
Geographic location
Date collected
Date created
Subject
Organisational unit
Notes
Funding
204320 - Unique Sink Orientations (SNF)