All ternary permutation constraint satisfaction problems parameterized above average have kernels with quadratic numbers of variables

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

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-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 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, Proceedings
Number of pages12
Volume6346 LNCS
Publication date2010
EditionPART 1
Pages326-337
ISBN (Print)3642157742, 9783642157745
DOIs
Publication statusPublished - 2010
Event18th Annual European Symposium on Algorithms, ESA 2010 - Liverpool, United Kingdom
Duration: 6. Sep 20108. Sep 2010

Conference

Conference18th Annual European Symposium on Algorithms, ESA 2010
Country/TerritoryUnited Kingdom
CityLiverpool
Period06/09/201008/09/2010
SponsorEuropean Association of Theoretical Computer Science, International Society of Computational Geometry, London Mathematical Society, Springer, University of Liverpool
SeriesLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
NumberPART 1
Volume6346 LNCS
ISSN0302-9743

Fingerprint

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

Cite this