## Details

Original language | English |
---|---|

Pages (from-to) | 737-758 |

Number of pages | 22 |

Journal | Theory of Computing Systems |

Volume | 60 |

Issue number | 4 |

Early online date | 13 Sept 2016 |

Publication status | Published - 1 May 2017 |

## Abstract

The aim of the paper is to examine the computational complexity and algorithmics of enumeration, the task to output all solutions of a given problem, from the point of view of parameterized complexity. First, we define formally different notions of efficient enumeration in the context of parameterized complexity: FPT-enumeration and delayFPT. Second, we show how different algorithmic paradigms can be used in order to get parameter-efficient enumeration algorithms in a number of examples. These paradigms use well-known principles from the design of parameterized decision as well as enumeration techniques, like for instance kernelization and self-reducibility. The concept of kernelization, in particular, leads to a characterization of fixed-parameter tractable enumeration problems. Furthermore, we study the parameterized complexity of enumerating all models of Boolean formulas having weight at least k, where k is the parameter, in the famous Schaefer’s framework. We consider propositional formulas that are conjunctions of constraints taken from a fixed finite set Γ. Given such a formula and an integer k, we are interested in enumerating all the models of the formula that have weight at least k. We obtain a dichotomy classification and prove that, according to the properties of the constraint language Γ, either one can enumerate all such models in delayFPT, or no such delayFPT enumeration algorithm exists under some complexity-theoretic assumptions.

## Keywords

- Algorithms, Enumeration, Kernel, Parameterized complexity, Parameterized enumeration, Self-reducibility

## ASJC Scopus subject areas

- Mathematics(all)
**Theoretical Computer Science**- Computer Science(all)
**Computational Theory and Mathematics**

## Cite this

- Standard
- Harvard
- Apa
- Vancouver
- BibTeX
- RIS

**Paradigms for Parameterized Enumeration.**/ Creignou, Nadia; Meier, Arne; Müller, Julian Steffen et al.

In: Theory of Computing Systems, Vol. 60, No. 4, 01.05.2017, p. 737-758.

Research output: Contribution to journal › Article › Research › peer review

*Theory of Computing Systems*, vol. 60, no. 4, pp. 737-758. https://doi.org/10.1007/s00224-016-9702-4

*Theory of Computing Systems*,

*60*(4), 737-758. https://doi.org/10.1007/s00224-016-9702-4

}

TY - JOUR

T1 - Paradigms for Parameterized Enumeration

AU - Creignou, Nadia

AU - Meier, Arne

AU - Müller, Julian Steffen

AU - Schmidt, Johannes

AU - Vollmer, Heribert

N1 - Funding information: A preliminary version of this paper appeared in the proceedings of MFCS 2013, LNCS 8087, pp. 290–301. This work was supported by a Campus France/DAAD Procope grant, Campus France Projet No 28292TE, DAAD Projekt-ID 55892324, and by the French Agence Nationale de la Recherche, AGGREG project reference ANR-14-CE25-0017.

PY - 2017/5/1

Y1 - 2017/5/1

N2 - The aim of the paper is to examine the computational complexity and algorithmics of enumeration, the task to output all solutions of a given problem, from the point of view of parameterized complexity. First, we define formally different notions of efficient enumeration in the context of parameterized complexity: FPT-enumeration and delayFPT. Second, we show how different algorithmic paradigms can be used in order to get parameter-efficient enumeration algorithms in a number of examples. These paradigms use well-known principles from the design of parameterized decision as well as enumeration techniques, like for instance kernelization and self-reducibility. The concept of kernelization, in particular, leads to a characterization of fixed-parameter tractable enumeration problems. Furthermore, we study the parameterized complexity of enumerating all models of Boolean formulas having weight at least k, where k is the parameter, in the famous Schaefer’s framework. We consider propositional formulas that are conjunctions of constraints taken from a fixed finite set Γ. Given such a formula and an integer k, we are interested in enumerating all the models of the formula that have weight at least k. We obtain a dichotomy classification and prove that, according to the properties of the constraint language Γ, either one can enumerate all such models in delayFPT, or no such delayFPT enumeration algorithm exists under some complexity-theoretic assumptions.

AB - The aim of the paper is to examine the computational complexity and algorithmics of enumeration, the task to output all solutions of a given problem, from the point of view of parameterized complexity. First, we define formally different notions of efficient enumeration in the context of parameterized complexity: FPT-enumeration and delayFPT. Second, we show how different algorithmic paradigms can be used in order to get parameter-efficient enumeration algorithms in a number of examples. These paradigms use well-known principles from the design of parameterized decision as well as enumeration techniques, like for instance kernelization and self-reducibility. The concept of kernelization, in particular, leads to a characterization of fixed-parameter tractable enumeration problems. Furthermore, we study the parameterized complexity of enumerating all models of Boolean formulas having weight at least k, where k is the parameter, in the famous Schaefer’s framework. We consider propositional formulas that are conjunctions of constraints taken from a fixed finite set Γ. Given such a formula and an integer k, we are interested in enumerating all the models of the formula that have weight at least k. We obtain a dichotomy classification and prove that, according to the properties of the constraint language Γ, either one can enumerate all such models in delayFPT, or no such delayFPT enumeration algorithm exists under some complexity-theoretic assumptions.

KW - Algorithms

KW - Enumeration

KW - Kernel

KW - Parameterized complexity

KW - Parameterized enumeration

KW - Self-reducibility

UR - http://www.scopus.com/inward/record.url?scp=84987638662&partnerID=8YFLogxK

U2 - 10.1007/s00224-016-9702-4

DO - 10.1007/s00224-016-9702-4

M3 - Article

AN - SCOPUS:84987638662

VL - 60

SP - 737

EP - 758

JO - Theory of Computing Systems

JF - Theory of Computing Systems

SN - 1432-4350

IS - 4

ER -