mathematics Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...

, a unique sink orientation is an orientation of the edges of a

polytope In elementary geometry, a polytope is a geometric object with flat sides (''faces''). Polytopes are the generalization of three-dimensional polyhedra to any number of dimensions. Polytopes may exist in any general number of dimensions as an -d ...

such that, in every face of the polytope (including the whole polytope as one of the faces), there is exactly one

vertex Vertex, vertices or vertexes may refer to: Science and technology Mathematics and computer science *Vertex (geometry), a point where two or more curves, lines, or edges meet *Vertex (computer graphics), a data structure that describes the position ...

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 program Linear programming (LP), also called linear optimization, is a method to achieve the best outcome (such as maximum profit or lowest cost) in a mathematical model whose requirements are represented by linear relationships. Linear programming is ...

s as well as certain nonlinear programs such as the

smallest circle problem The smallest-circle problem (also known as minimum covering circle problem, bounding circle problem, least bounding circle problem, smallest enclosing circle problem) is a mathematical problem of computing the smallest circle that contains all of ...

In hypercubes

The problem of finding the sink in a unique sink orientation of a hypercube was formulated as an abstraction of

linear complementarity problem In mathematical optimization theory, the linear complementarity problem (LCP) arises frequently in computational mechanics and encompasses the well-known quadratic programming as a special case. It was proposed by Cottle and Dantzig in 1968. ...

s by and it was termed "unique sink orientation" in 2001 . It is possible for an

algorithm In mathematics and computer science, an algorithm () is a finite sequence of rigorous instructions, typically used to solve a class of specific Computational problem, problems or to perform a computation. Algorithms are used as specificat ...

to determine the unique sink of a -dimensional hypercube in time for , substantially smaller than the time required to examine all vertices. When the orientation has the additional property that the orientation forms a

directed acyclic graph In mathematics, particularly graph theory, and computer science, a directed acyclic graph (DAG) is a directed graph with no directed cycles. That is, it consists of vertices and edges (also called ''arcs''), with each edge directed from one ve ...

, which happens when unique sink orientations are used to model

LP-type problem In the study of algorithms, an LP-type problem (also called a generalized linear program) is an optimization problem that shares certain properties with low-dimensional linear programs and that may be solved by similar algorithms. LP-type problems i ...

s, it is possible to find the sink using a randomized algorithm in expected time exponential in the square root of ''d'' .

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, :

\sum_ 2^

where ''G''(''P'') is the graph of the polytope, and ''d''_in(''v'') is the

in-degree In mathematics, and more specifically in graph theory, a directed graph (or digraph) is a graph that is made up of a set of vertices connected by directed edges, often called arcs. Definition In formal terms, a directed graph is an ordered pai ...

(number of incoming edges) of a vertex ''v'' in the given orientation . 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 In graph theory, an acyclic orientation of an undirected graph is an assignment of a direction to each edge (an orientation) that does not form any directed cycle and therefore makes it into a directed acyclic graph. Every graph has an acyclic orie ...

, 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 In mathematics, an upper set (also called an upward closed set, an upset, or an isotone set in ''X'') of a partially ordered set (X, \leq) is a subset S \subseteq X with the following property: if ''s'' is in ''S'' and if ''x'' in ''X'' is larger ...

for at least one acyclic unique sink orientation. In this way, the

face lattice A convex polytope is a special case of a polytope, having the additional property that it is also a convex set contained in the n-dimensional Euclidean space \mathbb^n. Most texts. use the term "polytope" for a bounded convex polytope, and the wo ...

of the polytope is uniquely determined from the graph . Based on this structure, the face lattices of simple polytopes can be reconstructed from their graphs in

polynomial time In computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by ...

using

linear programming Linear programming (LP), also called linear optimization, is a method to achieve the best outcome (such as maximum profit or lowest cost) in a mathematical model whose requirements are represented by linear function#As a polynomial function, li ...

References

*. *. *. *. *. *. *{{citation , last1 = Gärtner , first1 = Bernd , title = The Random-Facet simplex algorithm on combinatorial cubes , journal = Random Structures & Algorithms , pages = 353–381 , volume = 20 , year = 2002 , issue = 3 , doi = 10.1002/rsa.10034 . Graph theory objects Polyhedral combinatorics