A probabilistic approach to problems parameterized above or below tight bounds

DOI10.1016/j.jcss.2010.06.001zbMath1209.68277OpenAlexW2107546895MaRDI QIDQ632807

Eun Jung Kim, Stefan Szeider, Anders Yeo, Gregory Gutin

Publication date: 28 March 2011

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

zbMATH Keywords

kernelprobabilistic methodhypercontractive inequalityfixed-parameter tractableabove tight boundsparameterized problems

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph algorithms (graph-theoretic aspects) (05C85) Directed graphs (digraphs), tournaments (05C20) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Related Items (12)

Kernelization – Preprocessing with a Guarantee ⋮ 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 satisfying almost all linear equations over \(\mathbb F_2\) ⋮ Parameterized complexity of MaxSat above average ⋮ Unnamed Item ⋮ Confronting intractability via parameters ⋮ Beyond Max-Cut: \(\lambda\)-extendible properties parameterized above the Poljak-Turzík bound ⋮ Hypercontractive inequality for pseudo-Boolean functions of bounded Fourier width ⋮ Kernels for below-upper-bound parameterizations of the hitting set and directed dominating set problems ⋮ Polynomial kernels for vertex cover parameterized by small degree modulators ⋮ Acyclic Digraphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Note on Max Lin-2 above average
• Fixed-parameter complexity of minimum profile problems
• Parameterizing above or below guaranteed values
• Solving linear equations over GF(2): Block Lanczos algorithm
• 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)\)
• Systems of Linear Equations over $\mathbb{F}_2$ and Problems Parameterized above Average
• All Ternary Permutation Constraint Satisfaction Problems Parameterized above Average Have Kernels with Quadratic Numbers of Variables
• Interval Completion Is Fixed Parameter Tractable
• Logarithmic Sobolev Inequalities
• Parameterizing above Guaranteed Values: MaxSat and MaxCut
• Algorithms with large domination ratio
• Digraphs
• On the advantage over a random assignment

This page was built for publication: A probabilistic approach to problems parameterized above or below tight bounds