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

DOI10.1007/978-3-642-15775-2_28MaRDI QIDQ3586474zbMATH OpenOpenAlexFDO

Authors G. Gutin, Leo Van Iersel, Matthias Mnich, A. Yeo

Publication date 6 September 2010

Published in Algorithms – ESA 2010 (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1004.1956

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Abstract: A ternary Permutation-CSP is specified by a subset $Pi$ of the symmetric group $mathcal{S}_3$. 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 $alpha$ of $V$ that maximizes the number of triples whose ordering (under $alpha$) follows a permutation in $Pi$. We prove that all ternary Permutation-CSPs parameterized above average have kernels with quadratic numbers of variables.

Recommendations

• Every ternary permutation constraint satisfaction problem parameterized above average has a kernel with a quadratic number of variables
• Improved parameterized algorithms for above average constraint satisfaction
• Parameterized constraint satisfaction problems: a survey
• Constraint Satisfaction Problems Parameterized above or below Tight Bounds: A Survey
• Parameterized algorithms for constraint satisfaction problems above average with global cardinality constraints

Cited in

(8)

• Betweenness parameterized above tight lower bound
• Improved parameterized algorithms for above average constraint satisfaction
• Kernelization -- preprocessing with a guarantee
• Every ternary permutation constraint satisfaction problem parameterized above average has a kernel with a quadratic number of variables
• Lower bounds on kernelization
• Domination above \(r\)-independence: does sparseness help?
• A probabilistic approach to problems parameterized above or below tight bounds
• Satisfying ternary permutation constraints by multiple linear orders or phylogenetic trees

This page was built for publication: All ternary permutation constraint satisfaction problems parameterized above average have kernels with quadratic numbers of variables

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3586474)