Reverse-search algorithms are a class of

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 ...

s for generating all objects of a given size, from certain classes of combinatorial objects. In many cases, these methods allow the objects to be generated 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 ...

per object, using only enough memory to store a constant number of objects (

polynomial space In computational complexity theory, PSPACE is the set of all decision problems that can be solved by a Turing machine using a polynomial amount of space. Formal definition If we denote by SPACE(''t''(''n'')), the set of all problems that can b ...

). (Generally, however, they are not classed as polynomial-time algorithms, because the number of objects they generate is exponential.) They work by organizing the objects to be generated into a

spanning tree In the mathematical field of graph theory, a spanning tree ''T'' of an undirected graph ''G'' is a subgraph that is a tree which includes all of the vertices of ''G''. In general, a graph may have several spanning trees, but a graph that is not ...

of their

state space A state space is the set of all possible configurations of a system. It is a useful abstraction for reasoning about the behavior of a given system and is widely used in the fields of artificial intelligence and game theory. For instance, the toy ...

, and then performing a

depth-first search Depth-first search (DFS) is an algorithm for traversing or searching tree or graph data structures. The algorithm starts at the root node (selecting some arbitrary node as the root node in the case of a graph) and explores as far as possible alon ...

of this tree. Reverse-search algorithms were introduced by

David Avis David Michael Avis (born March 20, 1951) is a Canadians, Canadian and United Kingdom, British computer scientist known for his contributions to geometric computations. Avis is a professor in computational geometry and applied mathematics in the S ...

and

Komei Fukuda Komei Fukuda ( ja, 福田公明, born 1951) is a Japanese mathematician known for his contributions to optimization, polyhedral computation and oriented matroid theory. Fukuda is a professor in optimization and computational geometry in the De ...

in 1991, for problems of generating the vertices of

convex polytope 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 ...

s and the cells of arrangements of hyperplanes. They were formalized more broadly by Avis and Fukuda in 1996.

Principles

A reverse-search algorithm generates the combinatorial objects in a

, an

implicit graph In the study of graph algorithms, an implicit graph representation (or more simply implicit graph) is a graph whose vertices or edges are not represented as explicit objects in a computer's memory, but rather are determined algorithmically from so ...

whose vertices are the objects to be listed and whose edges represent certain "local moves" connecting pairs of objects, typically by making small changes to their structure. It finds each objects using a

in a rooted

of this state space, described by the following information: *The root of the spanning tree, one of the objects *A subroutine for generating the parent of each object in the tree, with the property that if repeated enough times it will eventually reach the root *A subroutine for listing all of the neighbors in the state space (not all of which may be neighbors in the tree) From this information it is possible to find the children of any given node in the tree, reversing the links given by the parent subroutine: they are simply the neighbors whose parent is the given node. It is these reversed links to child nodes that the algorithm searches. A classical depth-first search of this spanning tree would traverse the tree recursively, starting from the root, at each node listing all of the children and making a recursive call for each one. Unlike a depth-first search of a graph with cycles, it is not necessary to maintain the set of already-visited nodes to avoid repeated visits; such repetition is not possible in a tree. However, this recursive algorithm may still require a large amount of memory for its

call stack In computer science, a call stack is a stack data structure that stores information about the active subroutines of a computer program. This kind of stack is also known as an execution stack, program stack, control stack, run-time stack, or ma ...

, in cases when the tree is very deep. Instead, reverse search traverses the spanning tree in the same order while only storing two objects: the current object of the traversal, and the previously traversed object. Initially, the current object is set to the root of the tree, and there is no previous object. From this information, it is possible to determine the next step of the traversal by the following case analysis: *If there is no previous object, or the previous object is the parent of the current object, then this is the first time the traversal has reached the current object, so it is output from the search. The next object is its first child or, if it has no children, its parent. *In all other cases, the previous object must be a child of the current object. The algorithm lists the children (that is, state-space neighbors of the current object that have the current object as their parent) one at a time until reaching this previous child, and then takes one more step in this list of children. If another child is found in this way, it is the next object. If there is no next child and the current object is not the root, the next object is the parent of the current object. In the remaining case, when there is no next child and the current object is the root, the reverse search terminates. This algorithm involves listing the neighbors of an object once for each step in the search. However, if there are

N

objects to be listed, then the search performs

2N-1

steps, so the number of times it generates neighbors of objects is within a factor of two of the number of times the recursive depth-first search would do the same thing.

Applications

Examples of the problems to which reverse search has been applied include the following combinatorial generation problems: ;Vertices of simple convex polytopes :If a

d

-dimensional

is defined as an intersection of half-spaces, then its vertices can be described as the points of intersection of

d

or more

hyperplane In geometry, a hyperplane is a subspace whose dimension is one less than that of its ''ambient space''. For example, if a space is 3-dimensional then its hyperplanes are the 2-dimensional planes, while if the space is 2-dimensional, its hyper ...

s bounding the halfspaces; it is a simple polytope if no vertex is the intersection of more than

d

of these hyperplanes. The

vertex enumeration problem In mathematics, the vertex enumeration problem for a polytope, a polyhedral cell complex, a hyperplane arrangement, or some other object of discrete geometry, is the problem of determination of the object's vertices given some formal representation ...

is the problem of listing all of these vertices. The edges of the polytope connect pairs of vertices that have

d-1

hyperplanes in common, so the vertices and edges form a state space in which each vertex has

d

neighbors. The

simplex algorithm In mathematical optimization, Dantzig's simplex algorithm (or simplex method) is a popular algorithm for linear programming. The name of the algorithm is derived from the concept of a simplex and was suggested by T. S. Motzkin. Simplices are n ...

from the theory of

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 ...

finds a vertex maximizing a given linear function of the coordinates, by walking from vertex to vertex, choosing at each step a vertex with a greater value of the function; there are several standard choices of "pivot rule" that specify more precisely which vertex to choose. Any such pivot rule can be interpreted as defining the parent function of a spanning tree of the polytope, whose root is the optimal vertex. Applying reverse search to this data generates all vertices of the polytope. A similar algorithm can also enumerate all bases of a linear program, without requiring that it defines a polytope that is simple. ;Cells of hyperplane arrangements :A

hyperplane arrangement In geometry and combinatorics, an arrangement of hyperplanes is an arrangement of a finite set ''A'' of hyperplanes in a linear, affine, or projective space ''S''. Questions about a hyperplane arrangement ''A'' generally concern geometrical, top ...

decomposes

Euclidean space Euclidean space is the fundamental space of geometry, intended to represent physical space. Originally, that is, in Euclid's Elements, Euclid's ''Elements'', it was the three-dimensional space of Euclidean geometry, but in modern mathematics ther ...

into cells, each described by a "sign vector" that describes whether its points belong to one of the hyperplanes (sign 0), are on one side of the hyperplane (sign +1), or are on the other side (sign −1). The cells form a connected state space under local moves that change a single sign by one unit, and it is possible to check that this operation produces a valid cell by solving a linear programming feasibility problem. A spanning tree can be constructed for any choice of root cell by defining a parent operator that makes the first possible change that would bring the sign vector closer to that of the root. Using reverse search for this state space and parent operator produces an algorithm for listing all cells in polynomial time per cell. ;Point-set triangulations :The triangulations of a planar point set are connected by "flip" moves that remove one diagonal from a triangulation and replace it by another. If the

Delaunay triangulation In mathematics and computational geometry, a Delaunay triangulation (also known as a Delone triangulation) for a given set P of discrete points in a general position is a triangulation DT(P) such that no point in P is inside the circumcircle o ...

is chosen as the root, then every triangulation can be flipped to the Delaunay triangulation by steps in which the triangulation of some subset of four points is replaced by its Delaunay triangulation. Choosing the first Delaunay flip as the parent of each triangulation, and applying local search, produces an algorithm for listing all triangulations in polynomial time per triangulation. ;Connected subgraphs :The connected subgraphs, and connected

induced subgraph In the mathematical field of graph theory, an induced subgraph of a graph is another graph, formed from a subset of the vertices of the graph and ''all'' of the edges (from the original graph) connecting pairs of vertices in that subset. Defini ...

s, of a given connected graph form a state space whose local moves are the addition or removal of a single edge or vertex of the graph, respectively. A spanning tree of this state space can be obtained by adding the first edge or vertex (in some ordering of the edges or vertices) whose addition produces another connected subgraph; its root is the whole graph. Applying local search to this state space and parent operator produces an algorithm for listing all connected subgraphs in polynomial time per subgraph. Other applications include algorithms for generating the following structures: *

Polyomino A polyomino is a plane geometric figure formed by joining one or more equal squares edge to edge. It is a polyform whose cells are squares. It may be regarded as a finite subset of the regular square tiling. Polyominoes have been used in pop ...

polyiamond A polyiamond (also polyamond or simply iamond, or sometimes triangular polyomino) is a polyform whose base form is an equilateral triangle. The word ''polyiamond'' is a back-formation from ''diamond'', because this word is often used to describe ...

prototile In the mathematical theory of tessellations, a prototile is one of the shapes of a tile in a tessellation. Definition A tessellation of the plane or of any other space is a cover of the space by closed shapes, called tiles, that have disjoint in ...

s, and

polyhex (mathematics) In recreational mathematics, a polyhex is a polyform with a regular hexagon (or 'hex' for short) as the base form, constructed by joining together 1 or more hexagons. Specific forms are named by their number of hexagons: ''monohex'', ''dihex'', ' ...

hydrocarbon In organic chemistry, a hydrocarbon is an organic compound consisting entirely of hydrogen and carbon. Hydrocarbons are examples of group 14 hydrides. Hydrocarbons are generally colourless and hydrophobic, and their odors are usually weak or ex ...

molecules. *

Topological ordering In computer science, a topological sort or topological ordering of a directed graph is a linear ordering of its vertices such that for every directed edge ''uv'' from vertex ''u'' to vertex ''v'', ''u'' comes before ''v'' in the ordering. For in ...

s of

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 ...

s, using a state space whose local moves reverse the ordering of two elements. *

Spanning tree In the mathematical field of graph theory, a spanning tree ''T'' of an undirected graph ''G'' is a subgraph that is a tree which includes all of the vertices of ''G''. In general, a graph may have several spanning trees, but a graph that is not ...

s of graphs, non-crossing spanning trees of planar point sets, and more generally bases of

matroid In combinatorics, a branch of mathematics, a matroid is a structure that abstracts and generalizes the notion of linear independence in vector spaces. There are many equivalent ways to define a matroid axiomatically, the most significant being ...

s, using a state space that swaps one edge for another. *

Euler tour In graph theory, an Eulerian trail (or Eulerian path) is a trail in a finite graph that visits every edge exactly once (allowing for revisiting vertices). Similarly, an Eulerian circuit or Eulerian cycle is an Eulerian trail that starts and ends ...

s in graphs. *The

maximal independent set In graph theory, a maximal independent set (MIS) or maximal stable set is an independent set that is not a subset of any other independent set. In other words, there is no vertex outside the independent set that may join it because it is max ...

s of

sparse graph In mathematics, a dense graph is a graph in which the number of edges is close to the maximal number of edges (where every pair of vertices is connected by one edge). The opposite, a graph with only a few edges, is a sparse graph. The distinction ...

s. *

Maximal planar graph In graph theory, a planar graph is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints. In other words, it can be drawn in such a way that no edges cross ...

s and

polyhedral graph In geometric graph theory, a branch of mathematics, a polyhedral graph is the undirected graph formed from the vertices and edges of a convex polyhedron. Alternatively, in purely graph-theoretic terms, the polyhedral graphs are the 3-vertex-con ...

s. *Non-crossing minimally rigid graphs on a given point set. * Surrounding polygons, polygons that have some of a given set of points as vertices and surround the rest, using a state space that adds or removes one vertex of the polygon. *Vertices or facets of the

Minkowski sum In geometry, the Minkowski sum (also known as dilation) of two sets of position vectors ''A'' and ''B'' in Euclidean space is formed by adding each vector in ''A'' to each vector in ''B'', i.e., the set : A + B = \. Analogously, the Minkowski ...

of convex polytopes. *The corners (multidegrees) of

monomial ideal In abstract algebra, a monomial ideal is an ideal generated by monomials in a multivariate polynomial ring over a field. A toric ideal is an ideal generated by differences of monomials (provided the ideal is a prime ideal). An affine or projectiv ...

References

{{reflist, refs= {{citation , last1 = Kurita , first1 = Kazuhiro , last2 = Wasa , first2 = Kunihiro , doi = 10.1016/j.tcs.2022.04.048 , journal =

Theoretical Computer Science Theoretical computer science (TCS) is a subset of general computer science and mathematics that focuses on mathematical aspects of computer science such as the theory of computation, lambda calculus, and type theory. It is difficult to circumsc ...

, mr = 4436557 , pages = 1–12 , title = Constant amortized time enumeration of Eulerian trails , volume = 923 , year = 2022, doi-access = free {{citation , last1 = Avis , first1 = David , author1-link = David Avis , last2 = Katoh , first2 = Naoki , last3 = Ohsaki , first3 = Makoto , last4 = Streinu , first4 = Ileana , author4-link = Ileana Streinu , last5 = Tanigawa , first5 = Shin-ichi , date = June 2007 , doi = 10.1007/s00373-007-0709-0 , issue = S1 , journal =

Graphs and Combinatorics ''Graphs and Combinatorics'' (ISSN 0911-0119, abbreviated ''Graphs Combin.'') is a peer-reviewed academic journal in graph theory, combinatorics, and discrete geometry published by Springer Japan. Its editor-in-chief is Katsuhiro Ota of Keio U ...

, pages = 117–134 , title = Enumerating non-crossing minimally rigid frameworks , url = https://www-cgrl.cs.mcgill.ca/~avis/doc/avis/AKOST06a.pdf , volume = 23 {{citation , last = Lawson , first = C. L. , publisher = Jet Propulsion Laboratory , series = Memo 299 , title = Generation of a triangular grid with applications to contour plotting , year = 1972 {{citation , last1 = Bayer , first1 = Dave , author1-link = Dave Bayer , last2 = Taylor , first2 = Amelia , doi = 10.1016/j.jsc.2009.05.002 , issue = 10 , journal =

Journal of Symbolic Computation The ''Journal of Symbolic Computation'' is a peer-reviewed monthly scientific journal covering all aspects of symbolic computation published by Academic Press and then by Elsevier. It is targeted to both mathematicians and computer scientists. It ...

, mr = 2543431 , pages = 1477–1486 , title = Reverse search for monomial ideals , volume = 44 , year = 2009, doi-access = free {{citation , last1 = Avis , first1 = David , author1-link = David Avis , last2 = Fukuda , first2 = Komei , author2-link = Komei Fukuda , doi = 10.1007/BF02293050 , issue = 3 , journal =

Discrete & Computational Geometry '' Discrete & Computational Geometry'' is a peer-reviewed mathematics journal published quarterly by Springer. Founded in 1986 by Jacob E. Goodman and Richard M. Pollack, the journal publishes articles on discrete geometry and computational geom ...

, mr = 1174359 , pages = 295–313 , title = A pivoting algorithm for convex hulls and vertex enumeration of arrangements and polyhedra , volume = 8 , year = 1992, doi-access = free ; preliminary version in Seventh Annual Symposium on Computational Geometry, 1991, {{doi, 10.1145/109648.109659 {{citation , last1 = Caporossi , first1 = Gilles , last2 = Hansen , first2 = Pierre , date = May 1998 , doi = 10.1021/ci970116n , issue = 4 , journal = Journal of Chemical Information and Computer Sciences , pages = 610–619 , title = Enumeration of polyhex hydrocarbons to

h=21

, volume = 38 {{citation , last1 = Horiyama , first1 = Takashi , last2 = Yamane , first2 = Shogo , editor1-last = Akiyama , editor1-first = Jin , editor1-link = Jin Akiyama , editor2-last = Jiang , editor2-first = Bo , editor3-last = Kano , editor3-first = Mikio , editor4-last = Tan , editor4-first = Xuehou , contribution = Generation of polyiamonds for p6 tiling by the reverse search , doi = 10.1007/978-3-642-24983-9_10 , mr = 2927314 , pages = 96–107 , publisher = Springer , series = Lecture Notes in Computer Science , title = Computational Geometry, Graphs and Applications - 9th International Conference, CGGA 2010, Dalian, China, November 3-6, 2010, Revised Selected Papers , volume = 7033 , year = 2010 {{citation , last1 = Liang , first1 = Xiaodong , last2 = Wang , first2 = Rui , last3 = Meng , first3 = Ji xiang , doi = 10.1007/s10878-015-9953-z , issue = 1 , journal = Journal of Combinatorial Optimization , mr = 3595411 , pages = 254–264 , title = Code for polyomino and computer search of isospectral polyominoes , volume = 33 , year = 2017 {{citation , last = Avis , first = David , author-link = David Avis , editor1-last = Kalai , editor1-first = Gil , editor1-link = Gil Kalai , editor2-last = Ziegler , editor2-first = Günter M. , editor2-link = Günter M. Ziegler , contribution = A revised implementation of the reverse search vertex enumeration algorithm , location = Basel , mr = 1785299 , pages = 177–198 , publisher = Birkhäuser , series = DMV Seminar , title = Polytopes—combinatorics and computation: Including papers from the DMV-Seminar "Polytopes and Optimization" held in Oberwolfach, November 1997 , volume = 29 , year = 2000 {{citation , last = Avis , first = David , author-link = David Avis , doi = 10.1007/s004539900067 , issue = 6 , journal =

Algorithmica ''Algorithmica'' received the highest possible ranking “A*”. External links Springer information
Computer science journals Springer Science+Business Media academic journals Monthly journals Publications established in 1986 English-langua ...

, mr = 1412663 , pages = 618–632 , title = Generating rooted triangulations without repetitions , volume = 16 , year = 1996 {{citation , last1 = Avis , first1 = David , author1-link = David Avis , last2 = Fukuda , first2 = Komei , author2-link = Komei Fukuda , doi = 10.1016/0166-218X(95)00026-N , issue = 1-3 , journal =

Discrete Applied Mathematics ''Discrete Applied Mathematics'' is a peer-reviewed scientific journal covering algorithmic and applied areas of discrete mathematics. It is published by Elsevier and the editor-in-chief is Endre Boros (Rutgers University). The journal was split ...

, mr = 1380066 , pages = 21–46 , title = Reverse search for enumeration , url = http://cgm.cs.mcgill.ca/~avis/doc/avis/AF96a.ps , volume = 65 , year = 1996, doi-access = free {{citation , last = Sibson , first = R. , author-link = Robin Sibson , doi = 10.1093/comjnl/21.3.243 , issue = 3 , journal =

The Computer Journal ''The Computer Journal'' is a peer-reviewed scientific journal covering computer science and information systems. Established in 1958, it is one of the oldest computer science research journals. It is published by Oxford University Press on beha ...

, mr = 0507358 , pages = 243–245 , title = Locally equiangular triangulations , volume = 21 , year = 1973, doi-access = free {{citation , last = Sleumer , first = Nora H. , issue = 2 , journal = Nordic Journal of Computing , mr = 1709978 , pages = 137–147 , title = Output-sensitive cell enumeration in hyperplane arrangements , volume = 6 , year = 1999 {{citation , last = Eppstein , first = David , author-link = David Eppstein , doi = 10.1145/1597036.1597042 , issue = 4 , journal =

ACM Transactions on Algorithms ''ACM Transactions on Algorithms'' (''TALG'') is a quarterly peer-reviewed scientific journal covering the field of algorithms. It was established in 2005 and is published by the Association for Computing Machinery. The editor-in-chief is Edith Co ...

, mr = 2571901 , page = A38:1–A38:14 , title = All maximal independent sets and dynamic dominance for sparse graphs , volume = 5 , year = 2009, arxiv = cs/0407036 {{citation , last1 = Deza , first1 = Antoine , last2 = Fukuda , first2 = Komei , author2-link = Komei Fukuda , last3 = Rosta , first3 = Vera , contribution = Wagner's theorem and combinatorial enumeration of 3-polytopes , mr = 1330480 , pages = 30–34 , series = RIMS Kôkyûroku Bessatsu , title = Proceedings of a symposium held at the Research Institute for Mathematical Sciences, Kyoto University, Kyoto, May 17–19, 1993 , volume = 872 , year = 1994 {{citation , last = Weibel , first = Christophe , editor1-last = Blelloch , editor1-first = Guy E. , editor1-link = Guy Blelloch , editor2-last = Halperin , editor2-first = Dan , contribution = Implementation and parallelization of a reverse-search algorithm for Minkowski sums , doi = 10.1137/1.9781611972900.4 , pages = 34–42 , publisher = Society for Industrial and Applied Mathematics , title = Proceedings of the Twelfth Workshop on Algorithm Engineering and Experiments, ALENEX 2010, Austin, Texas, USA, January 16, 2010 , year = 2010, doi-access = free {{citation , last1 = Yamanaka , first1 = Katsuhisa , last2 = Avis , first2 = David , author2-link = David Avis , last3 = Horiyama , first3 = Takashi , last4 = Okamoto , first4 = Yoshio , last5 = Uehara , first5 = Ryuhei , last6 = Yamauchi , first6 = Tanami , doi = 10.1016/j.dam.2020.03.034 , journal =

, mr = 4310502 , pages = 305–313 , title = Algorithmic enumeration of surrounding polygons , url = http://cgm.cs.mcgill.ca/~avis/doc/avis/YAHOUY20.pdf , volume = 303 , year = 2021 {{citation , last = Fukuda , first = Komei , author-link = Komei Fukuda , doi = 10.1016/j.jsc.2003.08.007 , issue = 4 , journal =

, mr = 2094220 , pages = 1261–1272 , title = From the zonotope construction to the Minkowski addition of convex polytopes , volume = 38 , year = 2004, doi-access = free Search algorithms Combinatorial algorithms