# Incremental FPT Delay
## 1 Introduction  
### Enumeration  
In 1988, [PERSON], [PERSON], and [PERSON] [1] laid the cornerstone of enumeration algorithms. In modern times of ubiquitous computing, such algorithms are of central importance in several areas of life and research such as combinatorics, computational geometry, and operations research [2]. Beyond that, recent results unveil major importance in web search, data mining, bioinformatics, and computational linguistics [3]. Moreover, there are connections to formal languages on enumeration problems for probabilistic automata [4].  
Clearly, for enumeration algorithms, one is not primarily interested in their runtime complexity, whereas the time elapsed between two consecutive outputs of such an algorithm is of utmost interest. As a result, one measures the _delay_ of such algorithms. The main goal is to achieve a uniform stream of printed solutions. In this context, the complexity class DelayP, that is, polynomial delay, is regarded as an efficient way of enumeration. Enumeration algorithms for problems in that particular class print every \(p(|x|)\)-many-steps a new and distinct solution (where \(x\) is the input and \(p\) is a fixed polynomial). Interestingly, there is exists a class of _incremental polynomial delay_, IncP, which contains problems that allow for enumeration algorithms whose delay increases in the process of computation. Intuitively, this capturesthe idea that after printing 'obvious' solutions, later in the process, it becomes difficult to find new outputs. More precisely, the delay between output \(i\) and \(i+1\) is bounded by a polynomial in the input length _and in \(i\)_. Consequently, in the beginning, such an algorithm possesses a polynomial delay, whereas later, it eventually becomes exponential (for problems with exponentially many solutions, which is rather a common phenomenon). While prominent problems in the class DelayP are the enumeration of satisfying assignments for Horn or Krom formulas [5], the enumeration of structures for first-order query problems with possibly free second-order variables and at most one existential quantifier [6], or the enumeration of cycles in graphs [7], rather a limited amount of research has been invested in understanding IncP. A well-studied problem in this enumeration complexity class is the task of generating all maximal solutions of systems of equations modulo 2 [8]. Even today, it is not clear whether this problem can be solved with a polynomial delay. Another example of problems in IncP is the task to enumerate conjuncts in the context of monotone dualization of DNF formulas investigated by [PERSON] et al. [9], and [PERSON] and [PERSON] [10]. The significance of these results stems from the connection to computing minimal hypergraph transversals. A more recent result, which is not known to be in DelayP and not equivalent to the enumeration of transversals in hypergraphs of fixed edge size, was shown to be a member of IncP by [PERSON] et al. [11]: the task to enumerate all minimal triangulations of a given graph. In 2017, [PERSON] and [PERSON] [12] investigated IncP and its relationship to other classical enumeration classes in depth, greatly improving the overall understanding of incremental polynomial delay. One of their central results for this paper shows that if the function variant of NP restricted to total functions coincides with FP, then we have a collapse of incremental polynomial time with OutputP, the class of problems for which all solutions can be enumerated in time polynomial in the input length and in the solution set size (see Proposition 4 on page 4). Furthermore, [PERSON] and [PERSON] studied exponent sliced versions of incremental time and showed that this hierarchy of classes strictly interleaves ([12], Proposition 16).