{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,12]],"date-time":"2025-10-12T02:51:30Z","timestamp":1760237490343,"version":"build-2065373602"},"reference-count":44,"publisher":"MDPI AG","issue":"5","license":[{"start":{"date-parts":[[2020,5,15]],"date-time":"2020-05-15T00:00:00Z","timestamp":1589500800000},"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"],"award-info":[{"award-number":["247444366"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>In this paper, we study the relationship of parameterized enumeration complexity classes defined by Creignou et al. (MFCS 2013). Specifically, we introduce two hierarchies (IncFPTa and CapIncFPTa) of enumeration complexity classes for incremental fpt-time in terms of exponent slices and show how they interleave. Furthermore, we define several parameterized function classes and, in particular, introduce the parameterized counterpart of the class of nondeterministic multivalued functions with values that are polynomially verifiable and guaranteed to exist, TFNP, known from Megiddo and Papadimitriou (TCS 1991). We show that this class TF(para-NP), the restriction of the function variant of NP to total functions, collapsing to F(FPT), the function variant of FPT, is equivalent to the result that OutputFPT coincides with IncFPT. In addition, these collapses are shown to be equivalent to TFNP = FP, and also equivalent to P equals NP intersected with coNP. Finally, we show that these two collapses are equivalent to the collapse of IncP and OutputP in the classical setting. These results are the first direct connections of collapses in parameterized enumeration complexity to collapses in classical enumeration complexity, parameterized function complexity, classical function complexity, and computational complexity theory.<\/jats:p>","DOI":"10.3390\/a13050122","type":"journal-article","created":{"date-parts":[[2020,5,15]],"date-time":"2020-05-15T10:53:59Z","timestamp":1589540039000},"page":"122","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Incremental FPT Delay"],"prefix":"10.3390","volume":"13","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-8061-5376","authenticated-orcid":false,"given":"Arne","family":"Meier","sequence":"first","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":[[2020,5,15]]},"reference":[{"key":"ref_1","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_2","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":"Discrete Appl. Math."},{"key":"ref_3","first-page":"120","article-title":"Enumerating All Solutions of a Boolean CSP by Non-decreasing Weight","volume":"Volume 6695","author":"Sakallah","year":"2011","journal-title":"Theory and Applications of Satisfiability Testing, Proceedings of the 14th International Conference, SAT 2011, Ann Arbor, MI, USA, 19\u201322 June 2011"},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"532","DOI":"10.1007\/s00224-012-9442-z","article-title":"On Enumerating Monomials and Other Combinatorial Structures by Polynomial Interpolation","volume":"53","author":"Strozecki","year":"2013","journal-title":"Theory Comput. Syst."},{"key":"ref_5","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. Inform. Appl."},{"key":"ref_6","first-page":"189","article-title":"Enumeration Complexity of Logical Query Problems with Second-order Variables","volume":"Volume 12","author":"Bezem","year":"2011","journal-title":"Computer Science Logic, Proceedings of the 25th International Workshop\/20th Annual Conference of the EACSL, CSL 2011, Bergen, Norway, 12\u201315 September 2011"},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"237","DOI":"10.1002\/net.1975.5.3.237","article-title":"Bounds on backtrack algorithms for listing cycles, paths, and spanning trees","volume":"5","author":"Read","year":"1975","journal-title":"Networks"},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"966","DOI":"10.1137\/S0895480103428338","article-title":"On the Complexity of Some Enumeration Problems for Matroids","volume":"19","author":"Khachiyan","year":"2005","journal-title":"SIAM J. Discret. Math."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"514","DOI":"10.1137\/S009753970240639X","article-title":"New Results on Monotone Dualization and Generating Hypergraph Transversals","volume":"32","author":"Eiter","year":"2003","journal-title":"SIAM J. Comput."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"618","DOI":"10.1006\/jagm.1996.0062","article-title":"On the Complexity of Dualization of Monotone Disjunctive Normal Forms","volume":"21","author":"Fredman","year":"1996","journal-title":"J. Algorithms"},{"key":"ref_11","unstructured":"Sallinger, E., den Bussche, J.V., and Geerts, F. (2017, January 14\u201319). Efficiently Enumerating Minimal Triangulations. Proceedings of the 36th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems (PODS 2017), Chicago, IL, USA."},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"179","DOI":"10.1016\/j.dam.2018.06.038","article-title":"Incremental delay enumeration: Space and time","volume":"268","author":"Capelli","year":"2019","journal-title":"Discret. Appl. Math."},{"key":"ref_13","doi-asserted-by":"crossref","unstructured":"Downey, R.G., and Fellows, M.R. (2013). Fundamentals of Parameterized Complexity, Springer.","DOI":"10.1007\/978-1-4471-5559-1"},{"key":"ref_14","doi-asserted-by":"crossref","unstructured":"Downey, R.G., and Fellows, M.R. (1999). Parameterized Complexity, Springer.","DOI":"10.1007\/978-1-4612-0515-9"},{"key":"ref_15","unstructured":"Flum, J., and Grohe, M. (2006). Parameterized Complexity Theory, Springer."},{"key":"ref_16","doi-asserted-by":"crossref","unstructured":"Niedermeier, R. (2006). Invitation to Fixed-Parameter Algorithms, Oxford University Press.","DOI":"10.1093\/acprof:oso\/9780198566076.001.0001"},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"26","DOI":"10.1016\/j.jalgor.2004.03.005","article-title":"Parameterized complexity: Exponential speed-up for planar graph problems","volume":"52","author":"Alber","year":"2004","journal-title":"J. Algorithms"},{"key":"ref_18","first-page":"290","article-title":"Paradigms for Parameterized Enumeration","volume":"Volume 8087","author":"Chatterjee","year":"2013","journal-title":"Mathematical Foundations of Computer Science 2013, Proceedings of the 38th International Symposium, MFCS 2013, Klosterneuburg, Austria, 26\u201330 August 2013"},{"key":"ref_19","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_20","first-page":"524","article-title":"Parameterized Enumeration for Modification Problems","volume":"Volume 8977","author":"Dediu","year":"2015","journal-title":"Language and Automata Theory and Applications, Proceedings of the 9th International Conference, LATA 2015, Nice, France, 2\u20136 March 2015"},{"key":"ref_21","doi-asserted-by":"crossref","unstructured":"Creignou, N., Ktari, R., Meier, A., M\u00fcller, J., Olive, F., and Vollmer, H. (2019). Parameterised Enumeration for Modification Problems. Algorithms, 12.","DOI":"10.3390\/a12090189"},{"key":"ref_22","unstructured":"Ferrarotti, F., and Woltran, S. (2018). Enumeration Complexity of Poor Man\u2019s Propositional Dependence Logic. Foundations of Information and Knowledge Systems, Proceedings of the 10thInternational Symposium, FoIKS 2018, Budapest, Hungary, 14\u201318 May 2018, Springer. Lecture Notes in Computer Science."},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"317","DOI":"10.1016\/0304-3975(91)90200-L","article-title":"On Total Functions, Existence Theorems and Computational Complexity","volume":"81","author":"Megiddo","year":"1991","journal-title":"Theor. Comput. Sci."},{"key":"ref_24","first-page":"56","article-title":"Towards a Unified Complexity Theory of Total Functions","volume":"24","author":"Goldberg","year":"2017","journal-title":"Electron. Colloq. Comput. Complex. (ECCC)"},{"key":"ref_25","first-page":"181","article-title":"Parameterized Analogues of Probabilistic Computation","volume":"Volume 8959","author":"Ganguly","year":"2015","journal-title":"Algorithms and Discrete Applied Mathematics, Proceedings of the First International Conference, CALDAM 2015, Kanpur, India, 8\u201310 February 2015"},{"key":"ref_26","first-page":"130","article-title":"Default Logic and Bounded Treewidth","volume":"Volume 10792","author":"Klein","year":"2018","journal-title":"Language and Automata Theory and Applications Proceedings of the 12th International Conference, LATA 2018, Ramat Gan, Israel, 9\u201311 April 2018"},{"key":"ref_27","unstructured":"Bl\u00e4sius, T., Friedrich, T., Meeks, K., and Schirneck, M. (2018). On the Enumeration of Minimal Hitting Sets in Lexicographical Order. arXiv."},{"key":"ref_28","first-page":"387","article-title":"Counting and Enumeration Problems with Bounded Treewidth","volume":"Volume 6355","author":"Clarke","year":"2010","journal-title":"Logic for Programming, Artificial Intelligence, and Reasoning, Proceedings of the 16th International Conference, LPAR-16, Dakar, Senegal, 25 April\u20131 May 2010"},{"key":"ref_29","first-page":"52:1","article-title":"Efficient Enumeration of Solutions Produced by Closure Operations","volume":"Volume 47","author":"Ollinger","year":"2016","journal-title":"Proceedings of the 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016)"},{"key":"ref_30","doi-asserted-by":"crossref","first-page":"892","DOI":"10.1137\/S0097539703427203","article-title":"The Parameterized Complexity of Counting Problems","volume":"33","author":"Flum","year":"2004","journal-title":"SIAM J. Comput."},{"key":"ref_31","doi-asserted-by":"crossref","first-page":"147","DOI":"10.1016\/j.apal.2005.06.010","article-title":"Parameterized counting problems","volume":"138","author":"McCartin","year":"2006","journal-title":"Ann. Pure Appl. Log."},{"key":"ref_32","unstructured":"Chawla, S. (2020, January 5\u20138). Counting and Finding Homomorphisms is Universal for Parameterized Complexity Theory. Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms (SODA 2020), Salt Lake City, UT, USA."},{"key":"ref_33","doi-asserted-by":"crossref","first-page":"987","DOI":"10.1007\/s00224-018-9893-y","article-title":"Counting Edge-injective Homomorphisms and Matchings on Restricted Graph Classes","volume":"63","author":"Curticapean","year":"2019","journal-title":"Theory Comput. Syst."},{"key":"ref_34","first-page":"24:1","article-title":"Counting Induced Subgraphs: A Topological Approach to #W[1]-hardness","volume":"Volume 115","author":"Paul","year":"2018","journal-title":"Proceedings of the 13th International Symposium on Parameterized and Exact Computation (IPEC 2018)"},{"key":"ref_35","first-page":"26:1","article-title":"Counting Induced Subgraphs: An Algebraic Approach to #W[1]-hardness","volume":"Volume 138","author":"Rossmanith","year":"2019","journal-title":"Proceedings of the 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)"},{"key":"ref_36","unstructured":"Curticapean, R. (2015). The Simple, Little and Slow Things Count: On Parameterized Counting Complexity. [Ph.D. Thesis, Saarland University]."},{"key":"ref_37","doi-asserted-by":"crossref","unstructured":"Talbot, J.M., and Welsh, D.J.A. (2006). Complexity and Cryptography\u2014An Introduction, Cambridge University Press.","DOI":"10.1017\/CBO9780511755286"},{"key":"ref_38","first-page":"183","article-title":"On the Complexity of Hard Enumeration Problems","volume":"Volume 10168","author":"Drewes","year":"2017","journal-title":"Language and Automata Theory and Application, Proceedings of the 11th International Conference, LATA 2017, Ume\u00e5, Sweden, 6\u20139 March 2017"},{"key":"ref_39","unstructured":"Pippenger, N. (1997). Theories of Computability, Cambridge University Press."},{"key":"ref_40","unstructured":"Schmidt, J. (2009). Enumeration: Algorithms and Complexity. [Master\u2019s Thesis, Leibniz Universit\u00e4t Hannover]. Available online: http:\/\/citeseerx.ist.psu.edu\/viewdoc\/download?doi=10.1.1.582.8008&rep=rep1&type=pdf."},{"key":"ref_41","doi-asserted-by":"crossref","unstructured":"Fomin, F.V., and Kratsch, D. (2010). Exact Exponential Algorithms, Springer.","DOI":"10.1007\/978-3-642-16533-7"},{"key":"ref_42","doi-asserted-by":"crossref","first-page":"285","DOI":"10.1090\/S0002-9947-1965-0170805-7","article-title":"On the computational complexity of algorithms","volume":"117","author":"Hartmanis","year":"1965","journal-title":"Trans. Am. Math. Soc."},{"key":"ref_43","doi-asserted-by":"crossref","first-page":"97","DOI":"10.1137\/S0097539792228289","article-title":"The Complexity of Decision Versus Search","volume":"23","author":"Bellare","year":"1994","journal-title":"SIAM J. Comput."},{"key":"ref_44","doi-asserted-by":"crossref","first-page":"79","DOI":"10.1016\/0022-0000(88)90046-3","article-title":"How Easy is Local Search?","volume":"37","author":"Johnson","year":"1988","journal-title":"J. Comput. Syst. Sci."}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/13\/5\/122\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T09:29:13Z","timestamp":1760174953000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/13\/5\/122"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,5,15]]},"references-count":44,"journal-issue":{"issue":"5","published-online":{"date-parts":[[2020,5]]}},"alternative-id":["a13050122"],"URL":"https:\/\/doi.org\/10.3390\/a13050122","relation":{},"ISSN":["1999-4893"],"issn-type":[{"type":"electronic","value":"1999-4893"}],"subject":[],"published":{"date-parts":[[2020,5,15]]}}}