Unique sink orientation

In mathematics, a unique sink orientation is an orientation of the edges of a polytope such that, in every face of the polytope (including the whole polytope as one of the faces), there is exactly one vertex for which all adjoining edges are oriented inward (i.e. towards that vertex). If a polytope is given together with a linear objective function, and edges are oriented from vertices with smaller objective function values to vertices with larger objective values, the result is a unique sink orientation. Thus, unique sink orientations can be used to model linear programs as well as certain nonlinear programs such as the smallest circle problem.

In hypercubes

The problem of finding the sink in a unique sink orientation of a hypercube was formulated as an abstraction of linear complementarity problems by (Stickney Watson) and it was termed "unique sink orientation" in 2001 (Szabó Welzl). It is possible for an algorithm to determine the unique sink of a d-dimensional hypercube in time c^d for c < 2, substantially smaller than the 2^d time required to examine all vertices. When the orientation has the additional property that the orientation forms a directed acyclic graph, which happens when unique sink orientations are used to model LP-type problems, it is possible to find the sink using a randomized algorithm in expected time exponential in the square root of d (Gärtner 2002).

In simple polytopes

A simple d-dimensional polytope is a polytope in which every vertex has exactly d incident edges. In a unique-sink orientation of a simple polytope, every subset of k incoming edges at a vertex v determines a k-dimensional face for which v is the unique sink. Therefore, the number of faces of all dimensions of the polytope (including the polytope itself, but not the empty set) can be computed by the sum of the number of subsets of incoming edges,

[math]\displaystyle{ \sum_{v\in G(P)} 2^{d_{\operatorname{in}}(v)} }[/math]

where G(P) is the graph of the polytope, and d_in(v) is the in-degree (number of incoming edges) of a vertex v in the given orientation (Kalai 1988).

More generally, for any orientation of a simple polytope, the same sum counts the number of incident pairs of a face of the polytope and a sink of the face. And in an acyclic orientation, every face must have at least one sink. Therefore, an acyclic orientation is a unique sink orientation if and only if there is no other acyclic orientation with a smaller sum. Additionally, a k-regular subgraph of the given graph forms a face of the polytope if and only if its vertices form a lower set for at least one acyclic unique sink orientation. In this way, the face lattice of the polytope is uniquely determined from the graph (Kalai 1988). Based on this structure, the face lattices of simple polytopes can be reconstructed from their graphs in polynomial time using linear programming (Friedman 2009).

References

• Friedman, Eric J. (2009), "Finding a simple polytope from its graph in polynomial time", Discrete & Computational Geometry 41 (2): 249–256, doi:10.1007/s00454-008-9121-7 .
• "A simple way to tell a simple polytope from its graph", Journal of Combinatorial Theory, Series A 49 (2): 381–383, 1988, doi:10.1016/0097-3165(88)90064-7 .
• "The number of unique-sink orientations of the hypercube", Combinatorica 26 (1): 91–99, 2006, doi:10.1007/s00493-006-0007-0 .
• Schurr, Ingo; Szabó, Tibor (2004), "Finding the sink takes some time: an almost quadratic lower bound for finding the sink of unique sink oriented cubes", Discrete & Computational Geometry 31 (4): 627–642, doi:10.1007/s00454-003-0813-8 .
• Stickney, Alan; Watson, Layne (1978), "Digraph models of Bard-type algorithms for the linear complementarity problem", Mathematics of Operations Research 3 (4): 322–333, doi:10.1287/moor.3.4.322 .
• Szabó, Tibor (2001), "Unique sink orientations of cubes", 42nd IEEE Symposium on Foundations of Computer Science (Las Vegas, NV, 2001), Los Alamitos, CA: IEEE Computer Society, pp. 547–555, doi:10.1109/SFCS.2001.959931, ISBN 978-0-7695-1116-0 .
• Gärtner, Bernd (2002), "The Random-Facet simplex algorithm on combinatorial cubes", Random Structures & Algorithms 20 (3): 353–381, doi:10.1002/rsa.10034 .