All ternary permutation constraint satisfaction problems parameterized above average have polynomial kernels

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

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

9 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 all ternary Permutation-CSPs parameterized above average have kernels with quadratic numbers of variables.
Original languageEnglish
Title of host publicationAlgorithms - ESA 2010 (18th Annual European Symposium, Liverpool, UK, September 6-8, 2010. Proceedings, Part I)
EditorsM. Berg, de, U. Meyer
Place of PublicationBerlin
PublisherSpringer
Pages326-337
ISBN (Print)978-3-642-15774-5
DOIs
Publication statusPublished - 2010

Publication series

NameLecture Notes in Computer Science
Volume6346
ISSN (Print)0302-9743

Fingerprint Dive into the research topics of 'All ternary permutation constraint satisfaction problems parameterized above average have polynomial kernels'. Together they form a unique fingerprint.

Cite this