# Parameterised Enumeration for Modification Problems +
## 1 Introduction  
Given a computational problem one often is interested in generating all solutions. For instance, one wants to list all answers to a query to a database [1] or is interested in all hits that a web search engine produces [2]. Even in bioinformatics [3] or computational linguistics [4] such enumeration problems play a crucial role. In this setting, one is more interested in the delay between output solutions rather than in the overall runtime of such algorithms. Here, a uniform stream of solutions is highly desired. [PERSON] et al. [5] explain in their seminal paper that the notion of the complexity class DelayP, which consists of problems whose delay is bounded by a polynomial in the input length, is very important. A view on studied enumeration problems fuels the observation that often a specific order in the output solutions is very central: Many applications benefit from printing \"cheap\" solutions first. Moreover, enumerating all solutions in non-decreasing order allows to determine not only the smallest solution, but also the \(k\)th-smallest one. Such a generating algorithm allows finding the smallest solution obeying further constraints (at each generation step one verifies which constraints match). Unfortunately, this technique cannot guarantee efficient enumeration because a long prefix ofcandidates may not satisfy them. Yet, this technique is very versatile due to its applicability to any additional decidable constraint [6]. Now, we want to exemplify this observation. [PERSON] and [PERSON] [7] studied, within the well-known Schaefer framework for Boolean constraint satisfaction problems [8], which classes of propositional CNF formulas enumerating all satisfying solutions is possible in DelayP. They showed that for the classes of Horn, anti-Horn, affine or bijunctive formulas, such an algorithm exists. However, for any other class of formulas, having a DelayP algorithm implies \(\mathrm{P}=\mathrm{NP}\). Interestingly, their proof builds on the self-reducibility of the propositional satisfiability problem. By the approach of a flashlight search, that is, trying first an assignment 0 and then 1, they observed that their enumeration algorithm obeys lexicographic order. Later, [PERSON] et al. [9] studied enumerating satisfying assignments for propositional formulas in non-decreasing weight. Surprisingly, now, efficiently enumerating is only possible for Horn formulas and width-2 affine formulas (that is, affine formulas with at most two literals per clause). To achieve their result, the authors exploited priority queues to ensure enumeration in order (as was observed already by [PERSON] et al. [5]). While parameterised enumeration had already been considered before (see, e.g., the works of [PERSON], [PERSON] and [PERSON] et al. [10; 11; 12]), the notion of fixed-parameter tractable delay was novel, leading to the complexity class DelayFPT [13]. Intuitively, the \"polynomial time\" in the definition of DelayP here is substituted by a fixed-parameter runtime-bound of the form \(n^{O(1)}\cdot f(k)\), where \(n\) denotes the input length, \(k\) is the input parameter and \(f\) is a computable function. This introduces the notion of efficiency in the context of the parameterised world, that is, fixed-parameter tractability (FPT), to the enumeration framework. [PERSON] et al. [13] investigated a wealth of problems from propositional logic and developed enumeration algorithms based on self-reducibility and on the technique of kernelisation. Particularly, the membership of an enumeration problem in DelayFPT can be characterised by a specificly tailored form of kernelisability, very much as in the context of usual decision problems. As this area of parameterised enumeration is rather young and has received less attention, we want to further support this topic with this paper. Here, we study ordered enumeration in the context of parameterised complexity. First, we introduce arbitrary orders to the parameterised enumeration framework.