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.68122OpenAlexW2161806016MaRDI 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

permutationkernelsprobabilistic methodconstraint satisfactionparameterized complexity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (14)

Constraint Satisfaction Problems Parameterized above or below Tight Bounds: A Survey ⋮ Satisfying more than half of a system of linear equations over GF(2): a multivariate approach ⋮ Parameterized complexity of MaxSat above average ⋮ Unnamed Item ⋮ Detours in directed graphs ⋮ Satisfying ternary permutation constraints by multiple linear orders or phylogenetic trees ⋮ Going Far from Degeneracy ⋮ Confronting intractability via parameters ⋮ Unnamed Item ⋮ Hypercontractive inequality for pseudo-Boolean functions of bounded Fourier width ⋮ Linear kernels and linear-time algorithms for finding large cuts ⋮ Large Independent Sets in Subquartic Planar Graphs ⋮ Large Independent Sets in Triangle-Free Planar Graphs ⋮ Finding Detours is Fixed-Parameter Tractable

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Vertex cover problem parameterized above and below tight bounds
• Note on Max Lin-2 above average
• Fixed-parameter tractability and completeness II: On completeness for W[1]
• Fixed-parameter complexity of minimum profile problems
• Parameterizing above or below guaranteed values
• On problems without polynomial kernels
• Cyclic ordering is NP-complete
• A new approach to cyclic ordering of 2D orientations using ternary relation algebras
• Betweenness parameterized above tight lower bound
• The linear arrangement problem parameterized above guaranteed value
• Parametrized complexity theory.
• Étude des coefficients de Fourier des fonctions de \(L^ p(G)\)
• On Random Betweenness Constraints
• On Random Ordering Constraints
• A fixed-parameter algorithm for the directed feedback vertex set problem
• Systems of Linear Equations over $\mathbb{F}_2$ and Problems Parameterized above Average
• Kernel Bounds for Disjoint Cycles and Disjoint Paths
• Interval Completion Is Fixed Parameter Tractable
• Kernelization: New Upper and Lower Bound Techniques
• A Probabilistic Approach to Problems Parameterized above or below Tight Bounds
• Logarithmic Sobolev Inequalities
• Total Ordering Problem
• A Geometric Approach to Betweenness
• Parameterizing above Guaranteed Values: MaxSat and MaxCut
• Fixed-Parameter Tractability and Completeness I: Basic Results

This page was built for publication: Every ternary permutation constraint satisfaction problem parameterized above average has a kernel with a quadratic number of variables