Compactors for parameterized counting problems

Dimitrios M. Thilikos

Research output: Contribution to journalReview articlepeer-review


The concept of compactor has been introduced in Kim et al. (2018) as a general data-reduction concept for parametrized counting problems. For a function F: ς → N and a parameterization κ: ς → N a compactor (C, E) consists of a polynomial-time computable function P, called condenser, and a computable function M, called extractor, such that F = M P. If the size of P (x) is bounded by a polynomial function of κ (x), then we say that the compactor (C, E) is of polynomial size. Compactors can be seen as an attempt to formalize the notion of preprocessing for counting problems.

Original languageEnglish (US)
Article number100344
JournalComputer Science Review
StatePublished - Feb 2021


  • Compactor
  • Counting algorithms
  • Graph Algorithms
  • Parameterized algorithms

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'Compactors for parameterized counting problems'. Together they form a unique fingerprint.

Cite this