Parameterised Enumeration for Modification Problems

International audienceRecently, Creignou et al. (Theory Comput. Syst. 2017) have introduced the class 1 DelayFPT into parameterised complexity theory in order to capture the notion of efficiently solvable 2 parameterised enumeration problems. In this paper, we propose a framework for parameterised 3 ordered enumeration and will show how to obtain enumeration algorithms running with an FPT delay 4 in the context of general modification problems. We study these problems considering two different 5 orders of solutions, namely, lexicographic order and order by size. Furthermore, we present two 6 generic algorithmic strategies. The first one is based on the well-known principle of self-reducibility 7 and is used in the context of lexicographic order. The second one shows that the existence of a 8 neighbourhood structure among the solutions implies the existence of an algorithm running with 9 FPT delay which outputs all solutions ordered non-decreasingly by their size. 1