{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,13]],"date-time":"2026-02-13T14:46:55Z","timestamp":1770994015816,"version":"3.50.1"},"reference-count":45,"publisher":"MDPI AG","issue":"9","license":[{"start":{"date-parts":[[2019,9,9]],"date-time":"2019-09-09T00:00:00Z","timestamp":1567987200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["247444366 (ME 4279\/1-2)"],"award-info":[{"award-number":["247444366 (ME 4279\/1-2)"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001665","name":"Agence Nationale de la Recherche","doi-asserted-by":"publisher","award":["ANR-14-CE25-0017"],"award-info":[{"award-number":["ANR-14-CE25-0017"]}],"id":[{"id":"10.13039\/501100001665","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>Recently, Creignou et al. (Theory Comput. Syst. 2017), introduced the class DelayFPT into parameterised complexity theory in order to capture the notion of efficiently solvable parameterised enumeration problems. In this paper, we propose a framework for parameterised ordered enumeration and will show how to obtain enumeration algorithms running with an FPT delay in the context of general modification problems. We study these problems considering two different orders of solutions, namely, lexicographic order and order by size. Furthermore, we present two generic algorithmic strategies. The first one is based on the well-known principle of self-reducibility and is used in the context of lexicographic order. The second one shows that the existence of a neighbourhood structure among the solutions implies the existence of an algorithm running with FPT delay which outputs all solutions ordered non-decreasingly by their size.<\/jats:p>","DOI":"10.3390\/a12090189","type":"journal-article","created":{"date-parts":[[2019,9,9]],"date-time":"2019-09-09T11:26:17Z","timestamp":1568028377000},"page":"189","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":9,"title":["Parameterised Enumeration for Modification Problems"],"prefix":"10.3390","volume":"12","author":[{"given":"Nadia","family":"Creignou","sequence":"first","affiliation":[{"name":"Aix-Marseille Universit\u00e9, CNRS, LIS, 13003 Marseille, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ra\u00efda","family":"Ktari","sequence":"additional","affiliation":[{"name":"P\u00f4le technologique de Sfax, Universit\u00e9 de Sfax, Sfax 3000, Tunisia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8061-5376","authenticated-orcid":false,"given":"Arne","family":"Meier","sequence":"additional","affiliation":[{"name":"Institut f\u00fcr Theoretische Informatik, Leibniz Universit\u00e4t Hannover, 30167 Hannover, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Julian-Steffen","family":"M\u00fcller","sequence":"additional","affiliation":[{"name":"Institut f\u00fcr Theoretische Informatik, Leibniz Universit\u00e4t Hannover, 30167 Hannover, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Fr\u00e9d\u00e9ric","family":"Olive","sequence":"additional","affiliation":[{"name":"Aix-Marseille Universit\u00e9, CNRS, LIS, 13003 Marseille, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Heribert","family":"Vollmer","sequence":"additional","affiliation":[{"name":"Institut f\u00fcr Theoretische Informatik, Leibniz Universit\u00e4t Hannover, 30167 Hannover, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2019,9,9]]},"reference":[{"key":"ref_1","unstructured":"Hull, R., and Grohe, M. (2014, January 22\u201327). Enumerating answers to first-order queries over databases of low degree. Proceedings of the 33rd ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, PODS\u201914, Snowbird, UT, USA."},{"key":"ref_2","first-page":"557","article-title":"A Scalable Randomized Method to Compute Link-Based Similarity Rank on the Web Graph","volume":"Volume 3268","author":"Lindner","year":"2004","journal-title":"Proceedings of the Current Trends in Database Technology\u2014EDBT 2004 Workshops, EDBT 2004 Workshops PhD, DataX, PIM, P2P&DB, and ClustWeb, Heraklion"},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"2474","DOI":"10.1093\/bioinformatics\/bts423","article-title":"Algorithms and complexity of enumerating minimal precursor sets in genome-wide metabolic networks","volume":"28","author":"Milreu","year":"2012","journal-title":"Bioinformatics"},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"4289","DOI":"10.1016\/j.polymer.2007.05.018","article-title":"Computational linguistics: A new tool for exploring biopolymer structures and statistical mechanics","volume":"48","author":"Dill","year":"2007","journal-title":"Polymer"},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"119","DOI":"10.1016\/0020-0190(88)90065-8","article-title":"On Generating All Maximal Independent Sets","volume":"27","author":"Johnson","year":"1988","journal-title":"Inf. Process. Lett."},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"219","DOI":"10.1590\/S0101-74382005000200004","article-title":"An algorithm to generate all spanning trees of a graph in order of increasing cost","volume":"25","author":"Janssens","year":"2005","journal-title":"Pesqui. Oper."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"499","DOI":"10.1051\/ita\/1997310604991","article-title":"On generating all solutions of generalized satisfiability problems","volume":"31","author":"Creignou","year":"1997","journal-title":"Theor. Informatics Appl."},{"key":"ref_8","unstructured":"Lipton, R.J., Burkhard, W.A., Savitch, W.J., Friedman, E.P., and Aho, A.V. (1978, January 1\u20133). The Complexity of Satisfiability Problems. Proceedings of the 10th Annual ACM Symposium on Theory of Computing, San Diego, CA, USA."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"120","DOI":"10.1007\/978-3-642-21581-0_11","article-title":"Enumerating All Solutions of a Boolean CSP by Non-decreasing Weight","volume":"Volume 6695","author":"Creignou","year":"2011","journal-title":"Proceedings of the 14th International Conference on Theory and Applications of Satisfiability Testing, SAT 2011"},{"key":"ref_10","doi-asserted-by":"crossref","unstructured":"Fernau, H. (2002). On Parameterized Enumeration. Computing and Combinatorics, Springer.","DOI":"10.1007\/3-540-45655-4_60"},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"337","DOI":"10.1016\/j.tcs.2005.10.004","article-title":"Parameterized enumeration, transversals, and imperfect phylogeny reconstruction","volume":"351","author":"Damaschke","year":"2006","journal-title":"Theor. Comput. Sci."},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"1964","DOI":"10.1137\/12089051X","article-title":"A Polynomial Kernel for Proper Interval Vertex Deletion","volume":"27","author":"Fomin","year":"2013","journal-title":"SIAM J. Discret. Math."},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"737","DOI":"10.1007\/s00224-016-9702-4","article-title":"Paradigms for Parameterized Enumeration","volume":"60","author":"Creignou","year":"2017","journal-title":"Theory Comput. Syst."},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"173","DOI":"10.1016\/j.dam.2004.01.007","article-title":"Cluster graph modification problems","volume":"114","author":"Shamir","year":"2004","journal-title":"Discret. Appl. Math."},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"77","DOI":"10.1137\/0602010","article-title":"Computing the minimum fill-in is NP complete","volume":"2","author":"Yannakakis","year":"1981","journal-title":"SIAM J. Algebr. Discret. Methods"},{"key":"ref_16","doi-asserted-by":"crossref","unstructured":"Yannakakis, M. (1978, January 1\u20133). Node- and edge-deletion NP complete problems. Proceedings of the 10th Annual ACM Symposium on Theory of Computing, San Diego, CA, USA.","DOI":"10.1145\/800133.804355"},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"25","DOI":"10.1007\/s00453-003-1028-3","article-title":"Fixed-Parameter Algorithms for CLOSEST STRING and Related Problems","volume":"37","author":"Gramm","year":"2003","journal-title":"Algorithmica"},{"key":"ref_18","unstructured":"Williams, R., Gomes, C.P., and Selman, B. (2003, January 9\u201315). Backdoors To Typical Case Complexity. Proceedings of the IJCAI-03, Eighteenth International Joint Conference on Artificial Intelligence, Acapulco, Mexico."},{"key":"ref_19","first-page":"22:1","article-title":"On the Complexity of Enumerating the Answers to Well-designed Pattern Trees","volume":"Volume 48","author":"Martens","year":"2016","journal-title":"Proceedings of the 19th International Conference on Database Theory (ICDT 2016)"},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"61","DOI":"10.1016\/j.jcss.2019.02.004","article-title":"Parameterized aspects of triangle enumeration","volume":"103","author":"Bentert","year":"2019","journal-title":"J. Comput. Syst. Sci."},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"25","DOI":"10.1002\/mcda.1603","article-title":"Output-sensitive complexity of multiobjective combinatorial optimization","volume":"24","author":"Ehrgott","year":"2017","journal-title":"J. Multi-Criteria Decis. Anal."},{"key":"ref_22","doi-asserted-by":"crossref","unstructured":"Kr\u00f6ll, M., Pichler, R., and Woltran, S. (2017, January 19\u201325). On the Complexity of Enumerating the Extensions of Abstract Argumentation Frameworks. Proceedings of the 26th International Joint Conference on Artificial Intelligence, IJCAI 17, Melbourne, Australia.","DOI":"10.24963\/ijcai.2017\/159"},{"key":"ref_23","doi-asserted-by":"crossref","unstructured":"Carbonnel, C., and Hebrard, E. (2017, January 19\u201325). On the Kernelization of Global Constraints. Proceedings of the 26th International Joint Conference on Artificial Intelligence, IJCAI 2017, Melbourne, Australia, CA, USA, 2017.","DOI":"10.24963\/ijcai.2017\/81"},{"key":"ref_24","unstructured":"Schmidt, J. (2009). Enumeration: Algorithms and Complexity. [Master\u2019s Thesis, Leibniz Universit\u00e4t Hannover]."},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"287","DOI":"10.1017\/S0956796811000104","article-title":"Balancing weight-balanced trees","volume":"21","author":"Hirai","year":"2011","journal-title":"J. Funct. Program."},{"key":"ref_26","first-page":"38","article-title":"Graph Modification Problems (Dagstuhl Seminar 14071)","volume":"4","author":"Bodlaender","year":"2014","journal-title":"Dagstuhl Rep."},{"key":"ref_27","unstructured":"Garey, M.R., and Johnson, D.S. (1990). Computers and Intractability; A Guide to the Theory of NP-Completeness, W. H. Freeman & Co."},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"171","DOI":"10.1016\/0020-0190(96)00050-6","article-title":"Fixed-parameter tractability of graph modification problems for hereditary properties","volume":"58","author":"Cai","year":"1996","journal-title":"Inf. Process. Lett."},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"1906","DOI":"10.1137\/S0097539796303044","article-title":"Tractability of parameterized completion problems on chordal, strongly chordal, and proper interval graphs","volume":"28","author":"Kaplan","year":"1999","journal-title":"SIAM J. Comput."},{"key":"ref_30","unstructured":"Brandtst\u00e4dt, A., Le, V.B., and Spinrad, J.P. (1988). Graph Classes: A Survey, SIAM. Monographs on Discrete Applied Mathematics."},{"key":"ref_31","doi-asserted-by":"crossref","first-page":"21","DOI":"10.1016\/0166-218X(95)00026-N","article-title":"Reverse search for enumeration","volume":"65","author":"Avis","year":"1996","journal-title":"Discret. Appl. Math."},{"key":"ref_32","doi-asserted-by":"crossref","first-page":"113","DOI":"10.1007\/BF02679443","article-title":"On covering problems of codes","volume":"30","author":"Frances","year":"1997","journal-title":"Theory Comput. Syst."},{"key":"ref_33","unstructured":"Rossi, F. (2013, January 3\u20139). Backdoors to Abduction. Proceedings of the 23rd International Joint Conference on Artificial Intelligence, IJCAI 13, Beijing, China."},{"key":"ref_34","doi-asserted-by":"crossref","first-page":"64","DOI":"10.1016\/j.artint.2014.12.001","article-title":"Backdoors to tractable answer set programming","volume":"220","author":"Fichte","year":"2015","journal-title":"Artif. Intell."},{"key":"ref_35","doi-asserted-by":"crossref","first-page":"7:1","DOI":"10.1145\/2818646","article-title":"Backdoors to Normality for Disjunctive Logic Programs","volume":"17","author":"Fichte","year":"2015","journal-title":"ACM Trans. Comput. Log."},{"key":"ref_36","doi-asserted-by":"crossref","first-page":"157","DOI":"10.1016\/j.artint.2012.03.002","article-title":"Augmenting tractable fragments of abstract argumentation","volume":"186","author":"Ordyniak","year":"2012","journal-title":"Artif. Intell."},{"key":"ref_37","doi-asserted-by":"crossref","unstructured":"Fichte, J.K., Meier, A., and Schindler, I. (2016, January 5\u20138). Strong Backdoors for Default Logic. Proceedings of the 19th International Conference on Theory and Applications of Satisfiability Testing\u2014SAT 2016, Bordeaux, France.","DOI":"10.1007\/978-3-319-40970-2_4"},{"key":"ref_38","doi-asserted-by":"crossref","first-page":"476","DOI":"10.1007\/s00453-018-0515-5","article-title":"Backdoors for Linear Temporal Logic","volume":"81","author":"Meier","year":"2019","journal-title":"Algorithmica"},{"key":"ref_39","doi-asserted-by":"crossref","first-page":"49","DOI":"10.1016\/j.artint.2018.10.002","article-title":"Backdoors to planning","volume":"269","author":"Kronegger","year":"2019","journal-title":"Artif. Intell."},{"key":"ref_40","first-page":"36:1","article-title":"Combining Treewidth and Backdoors for CSP","volume":"Volume 66","author":"Vollmer","year":"2017","journal-title":"Proceedings of the 34th Symposium on Theoretical Aspects of Computer Science, STACS 2017"},{"key":"ref_41","doi-asserted-by":"crossref","first-page":"38","DOI":"10.1016\/j.jcss.2016.10.007","article-title":"Backdoors into heterogeneous classes of SAT and CSP","volume":"85","author":"Gaspers","year":"2017","journal-title":"J. Comput. Syst. Sci."},{"key":"ref_42","doi-asserted-by":"crossref","first-page":"509","DOI":"10.1007\/s00236-007-0056-x","article-title":"Solving #SAT using vertex covers","volume":"44","author":"Nishimura","year":"2007","journal-title":"Acta Inform."},{"key":"ref_43","first-page":"1","article-title":"Matched Formulas and Backdoor Sets","volume":"6","author":"Szeider","year":"2009","journal-title":"J. Satisf. Boolean Model. Comput."},{"key":"ref_44","doi-asserted-by":"crossref","first-page":"287","DOI":"10.1007\/978-3-642-30891-8_15","article-title":"Backdoors to Satisfaction","volume":"Volume 7370","author":"Gaspers","year":"2012","journal-title":"The Multivariate Algorithmic Revolution and Beyond"},{"key":"ref_45","unstructured":"Meier, A. (2018). Enumeration in Incremental FPT-Time. arXiv."}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/12\/9\/189\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T13:18:09Z","timestamp":1760188689000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/12\/9\/189"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,9,9]]},"references-count":45,"journal-issue":{"issue":"9","published-online":{"date-parts":[[2019,9]]}},"alternative-id":["a12090189"],"URL":"https:\/\/doi.org\/10.3390\/a12090189","relation":{},"ISSN":["1999-4893"],"issn-type":[{"value":"1999-4893","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,9,9]]}}}