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

DOI10.1016/j.jcss.2011.01.004zbMath1242.68122MaRDI QIDQ414863

Gregory Gutin, Anders Yeo, Matthias Mnich, Leo van Iersel

Publication date: 11 May 2012

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jcss.2011.01.004

zbMATH Keywords

permutation; kernels; probabilistic method; constraint satisfaction; parameterized complexity

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68T20: Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)