Complexity of Generation

In this talk I summarize the results obtained in 1999–2008 by Leonid Khachiyan, Endre Boros, Konrad Borys, Khaled Elbassiony, Kazuhisa Makino, and myself, on complexity of generation algorithms. These algorithms can be partitioned into three groups: supergraph, flash-light (backtrack), and dual-bounded generation. We will call a problem tractable if it can be solved by a polynomial (\(n^{const}\)) or quasi-polynomial (\(n^{polylog(n)}\)) time algorithm. More generally, for any positive non-decreasing function \(g = g(n)\), generating can be performed in total or incremental time g, or with g-delay. Most of the polynomial delay algorithms are provided by the flash-light (backtrack) method. As for the incremental algorithms, generating the next object is equivalent with just verifying its existence, which is a standard decision problem. Thus, incremental generation, in contrast to the delay one, may be NP-hard or NP-complete. For example, we show that generating all vertices of a polyhedron, given by its facets, is NP-complete (while the complexity status is still open in case of the polytopes, that is, bounded polyhedra). This problem is reduced to generating all negative cycles of a weighted digraph, which is NP-complete (for graphs, too). Generating all minimal transversals to a hypergraph, so-called dualization, plays an important role. For this problem an incremental quasi-polynomial algorithm (but no polynomial one) is known. We outline several wide classes of generation problems that can be reduced to dualization and, thus, solved in incremental quasi-polynomial time. We survey algorithms and complexity bounds for the above and many other generation problems.