Every ternary permutation constraint satisfaction problem parameterized above average has a kernel with a quadratic number of variables

Gregory Gutin*, Leo Van Iersel, Matthias Mnich, Anders Yeo

*Corresponding author for this work

Research output: Contribution to journalJournal articleResearchpeer-review

Abstract

A ternary Permutation-CSP is specified by a subset Π of the symmetric group S3. An instance of such a problem consists of a set of variables V and a multiset of constraints, which are ordered triples of distinct variables of V. The objective is to find a linear ordering α of V that maximizes the number of triples whose rearrangement (under α) follows a permutation in Π. We prove that every ternary Permutation-CSP parameterized above average has a kernel with a quadratic number of variables.

Original languageEnglish
JournalJournal of Computer and System Sciences
Volume78
Issue number1
Pages (from-to)151-163
ISSN0022-0000
DOIs
Publication statusPublished - 2012
Externally publishedYes

Keywords

  • Constraint satisfaction
  • Kernels
  • Parameterized complexity
  • Permutation
  • Probabilistic method

Fingerprint

Dive into the research topics of 'Every ternary permutation constraint satisfaction problem parameterized above average has a kernel with a quadratic number of variables'. Together they form a unique fingerprint.

Cite this