liu.seSearch for publications in DiVA
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Paradigms for Parameterized Enumeration
Aix Marseille University, France.
Leibniz University of Hannover, Germany.
Leibniz University of Hannover, Germany.
Linköping University, Department of Computer and Information Science, Software and Systems. Linköping University, Faculty of Science & Engineering.
Show others and affiliations
2017 (English)In: Theory of Computing Systems, ISSN 1432-4350, E-ISSN 1433-0490, Vol. 60, no 4, 737-758 p.Article in journal (Refereed) Published
Abstract [en]

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 Schaefers framework. We consider propositional formulas that are conjunctions of constraints taken from a fixed finite set I". 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 I", either one can enumerate all such models in delayFPT, or no such delayFPT enumeration algorithm exists under some complexity-theoretic assumptions.

Place, publisher, year, edition, pages
SPRINGER , 2017. Vol. 60, no 4, 737-758 p.
Keyword [en]
Parameterized complexity; Kernel; Enumeration; Parameterized enumeration; Algorithms; Self-reducibility
National Category
Computer Science
Identifiers
URN: urn:nbn:se:liu:diva-137086DOI: 10.1007/s00224-016-9702-4ISI: 000399178400007OAI: oai:DiVA.org:liu-137086DiVA: diva2:1093280
Note

Funding Agencies|Campus France/DAAD Procope grant, Campus France [28292TE]; DAAD Projekt [55892324]; French Agence Nationale de la Recherche, AGGREG project [ANR-14-CE25-0017]

Available from: 2017-05-05 Created: 2017-05-05 Last updated: 2017-05-05

Open Access in DiVA

No full text

Other links

Publisher's full text

Search in DiVA

By author/editor
Schmidt, Johannes
By organisation
Software and SystemsFaculty of Science & Engineering
In the same journal
Theory of Computing Systems
Computer Science

Search outside of DiVA

GoogleGoogle Scholar

Altmetric score

Total: 42 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf