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

G. Gutin, L.J.J. Iersel, van, M. Mnich, A. Yeo

Research output: Contribution to journalArticleAcademicpeer-review

22 Citations (Scopus)

Abstract

A ternary Permutation-CSP is specified by a subset ¿ of the symmetric group . 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 a of V that maximizes the number of triples whose rearrangement (under a) 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
Pages (from-to)151-163
JournalJournal of Computer and System Sciences
Volume78
Issue number1
DOIs
Publication statusPublished - 2012

Fingerprint

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

Cite this