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

doi:10.1016/j.jcss.2011.01.004

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

Research output: Contribution to journal › Article › peer-review

34 Citations (Scopus)

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 language	English
Pages (from-to)	151-163
Number of pages	13
Journal	Journal of Computer and System Sciences
Volume	78
Issue number	1
DOIs	https://doi.org/10.1016/j.jcss.2011.01.004
Publication status	Published - Jan 2012
Externally published	Yes

Keywords

Constraint satisfaction
Kernels
Parameterized complexity
Permutation
Probabilistic method

ASJC Scopus subject areas

Theoretical Computer Science
Computer Networks and Communications
Computational Theory and Mathematics
Applied Mathematics

Access to Document

10.1016/j.jcss.2011.01.004

Cite this

@article{76f6e99c7d4243ea88fa32ecc5f3250e,

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

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.",

keywords = "Constraint satisfaction, Kernels, Parameterized complexity, Permutation, Probabilistic method",

author = "Gregory Gutin and \{Van Iersel\}, Leo and Matthias Mnich and Anders Yeo",

year = "2012",

month = jan,

doi = "10.1016/j.jcss.2011.01.004",

language = "English",

volume = "78",

pages = "151--163",

journal = "Journal of Computer and System Sciences",

issn = "0022-0000",

publisher = "Academic Press Inc.",

number = "1",

}

TY - JOUR

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

AU - Gutin, Gregory

AU - Van Iersel, Leo

AU - Mnich, Matthias

AU - Yeo, Anders

PY - 2012/1

Y1 - 2012/1

N2 - 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.

AB - 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.

KW - Constraint satisfaction

KW - Kernels

KW - Parameterized complexity

KW - Permutation

KW - Probabilistic method

UR - https://www.scopus.com/pages/publications/81955168140

U2 - 10.1016/j.jcss.2011.01.004

DO - 10.1016/j.jcss.2011.01.004

M3 - Article

AN - SCOPUS:81955168140

SN - 0022-0000

VL - 78

SP - 151

EP - 163

JO - Journal of Computer and System Sciences

JF - Journal of Computer and System Sciences

IS - 1

ER -

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

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this