Summary: An enumeration problem is the task of listing a set of elements without redundancies, usually the solutions of some combinatorial problem. The enumeration of cycles in a graph appeared already 50 years ago [J. C. Tiernan, Commun. ACM 13, 722–726 (1970; Zbl 0225.94027)], while fundamental complexity notions for enumeration have been proposed 30 years ago by D. S. Johnson et al. [Inf. Process. Lett. 27, No. 3, 119–123 (1988; Zbl 0654.68086)]. Nowadays several research communities are working on enumeration from different point of views: graph algorithms, parametrized complexity, exact exponential algorithms, logic, database, enumerative combinatorics, applied algorithms to bioinformatics, cheminformatics, networks…
In the last ten years, the topic has attracted more attention and these different communities began to share their ideas and problems, as exemplified by two recent Dagstuhl workshops “Algorithmic enumeration: output-sensitive, input-sensitive, parameterized, approximative” and “Enumeration in data management” or the creation of Wikipedia pages for enumeration complexity and algorithms.
In this column, we focus on the structural complexity of enumeration, trying to capture different notions of tractability. The beautiful algorithmic methods used to solve enumeration problems are only briefly mentioned when relevant and would require another column. Much of what is presented here is inspired by several PhD theses and articles, in particular a good part of this text is borrowed from [F. Capelli and the author, Discrete Appl. Math. 268, 179–190 (2019; Zbl 1419.05014); “Enumerating models of DNF faster: breaking the dependency on the formula size”, Preprint, arXiv:1810.04006].