Unique Sink Orientations: Complexity, Structure and Algorithms
Antonis Thomas · Repository for Publications and Research Data (ETH Zurich) · 2017
In this thesis we study Unique Sink Orientations (USO).Those are useful combinatorial objects that serve as an abstraction to many optimization problems, such as Linear Programming.The concept of USO was originally introduced by Stickney and Watson [77], in the late 70s, in the context of mathematical programming.Afterwards, it was essentially forgotten until revived by Szabó and Welzl [78] in 2001.Since then, USO have been extensively studied and this thesis contains our small contributions towards better understanding the concept and how to use it as a tool in other contexts.A USO is an orientation of the n-dimensional hypercube graph such that every non-empty face induces a subgraph with a unique sink (in the graph theory sense, i.e. a vertex with only incoming edges).In particular, this implies that the whole cube has a unique sink, called global, since it is a face of itself.The graph that corresponds to a USO can either be cyclic or acyclic (in the latter case we call it an AUSO).The algorithmic problem is to find the global sink.The computational model assumes the existence of an oracle which, given a vertex, returns the orientation of its incident edges.The goal then is to minimize how many calls to this oracle are needed until the global sink is found.The v vi Abstract computational complexity of this problem is currently unsettled, with the best known algorithms being superpolynomial.In the language of USO, a polynomial-time algorithm is one that needs a polynomial number of oracle calls.