Enumeration algorithm

In computer science, an enumeration algorithm is an algorithm that enumerates the answers to a computational problem. Formally, such an algorithm applies to problems that take an input and produce a list of possible outputs, similarly to function problems. For each input, the enumeration algorithm must produce the list of all possible outputs, without duplicates, and then halt. The performance of an enumeration algorithm is measured in terms of the time required to produce the solutions, either in terms of the maximal delay between two consecutive solutions, or in terms of the total time required to produce all solutions. This complexity can be expressed in terms of the size of the input, the size of each individual output, or the total size of the set of all outputs, similarly to what is done with output-sensitive algorithms.

Common complexity classes

Enumeration problems have been studied in the context of computational complexity theory, and several complexity classes have been introduced for such problems.

A very general such class is EnumP, the class of problems for which the correctness of a possible output can be checked in polynomial time in the input and output. Formally, for such a problem, there must exist an algorithm A which takes as input the problem input x, the candidate output y, and solves the decision problem of whether y is a correct output for the input x, in polynomial time in x and y. For instance, this class contains all problems that amount to enumerating the witnesses of a problem in the class NP.

Other classes that have been defined include the following. In the case of problems that are also in EnumP, these problems are ordered from least to most specific

• Output polynomial, the class of problems whose complete output can be computed in polynomial time.
• Incremental polynomial time, the class of problems where, for all i, the i-th output can be produced in polynomial time in the input size and in the number i
• Polynomial delay, the class of problems where the delay between two consecutive outputs is polynomial in the input (and independent from the output)
• Strongly polynomial delay, the class of problems where the delay before each output is polynomial in the size of this specific output (and independent from the input or from the other outputs)
• Constant delay, the class of problems where the delay before each output is constant, i.e., independent from the input and output

Common techniques

• Flashlight search: In this technique, we enumerate solutions by exploring the space of all possible solutions (partitioning it at each successive step) and solving at each step the problem of whether the current partial solution can be completed to a partial solution. In particular, this technique applies to self-reducible problems.
• Closure: If we wish to enumerate the disjoint union of two sets, then we can solve the problem by enumerating the first set and then the second set. If the union is non disjoint but the sets can be enumerated in sorted order, then the enumeration can be performed in parallel on both sets while eliminating duplicates on the fly. If the union is not disjoint and both sets are not sorted then duplicates can be eliminated at the expense of a higher memory usage, e.g., using a hash table.

Examples of enumeration problems

• The vertex enumeration problem, where we are given a polytope described as a system of linear inequalities and we must enumerate the vertices of the polytope.
• Enumerating the minimal transversals of a hypergraph. This problem is related to monotone dualization and is connected to many applications in database theory and graph theory.
• Enumerating the answers to a database query, for instance a conjunctive query or a query expressed in monadic second-order. There have been characterizations in database theory of which conjunctive queries could be enumerated with constant delay.
• Enumerating maximal cliques in an input graph.
• Enumerating the satisfying assignments of representations of Boolean functions, e.g., a Boolean formula written in conjunctive normal form or disjunctive normal form, a binary decision diagram such as an OBDD, or a Boolean circuit in restricted classes studied in knowledge compilation, e.g., NNF.