Constraint Satisfaction Problems Parameterized above or below Tight Bounds: A Survey

DOI10.1007/978-3-642-30891-8_14zbMATH Open1358.68135arXiv1108.4803OpenAlexW1622068963MaRDI QIDQ2908541FDOQ2908541

Authors: G. Gutin, A. Yeo 

Publication date: 5 September 2012

Published in: The Multivariate Algorithmic Revolution and Beyond (Search for Journal in Brave)

Abstract: We consider constraint satisfaction problems parameterized above or below tight bounds. One example is MaxSat parameterized above $m/2$: given a CNF formula $F$ with $m$ clauses, decide whether there is a truth assignment that satisfies at least $m/2+k$ clauses, where $k$ is the parameter. Among other problems we deal with are MaxLin2-AA (given a system of linear equations over $mathbb{F}_2$ in which each equation has a positive integral weight, decide whether there is an assignment to the variables that satisfies equations of total weight at least $W/2+k$, where $W$ is the total weight of all equations), Max-$r$-Lin2-AA (the same as MaxLin2-AA, but each equation has at most $r$ variables, where $r$ is a constant) and Max-$r$-Sat-AA (given a CNF formula $F$ with $m$ clauses in which each clause has at most $r$ literals, decide whether there is a truth assignment satisfying at least $su{m}_{i=1}^m(1-2^{r_i})+k$ clauses, where $k$ is the parameter, $r_i$ is the number of literals in Clause $i$, and $r$ is a constant). We also consider Max-$r$-CSP-AA, a natural generalization of both Max-$r$-Lin2-AA and Max-$r$-Sat-AA, order (or, permutation) constraint satisfaction problems of arities 2 and 3 parameterized above the average value and some other problems related to MaxSat. We discuss results, both polynomial kernels and parameterized algorithms, obtained for the problems mainly in the last few years as well as some open questions.

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

Recommendations

• Parameterized constraint satisfaction problems: a survey
• scientific article; zbMATH DE number 1234562
• On constraint satisfaction problems below P
• On constraint satisfaction problems below P
• Parameterized complexity of constraint satisfaction problems
• Parameterized algorithms for constraint satisfaction problems above average with global cardinality constraints
• The approximability of constraint satisfaction problems
• Tractability in constraint satisfaction problems: a survey
• Artificial Intelligence: Methodology, Systems, and Applications

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Cites Work

• Title not available (Why is that?)
• On problems without polynomial kernels
• Almost 2-SAT is fixed-parameter tractable
• Betweenness parameterized above tight lower bound
• Parameterizing above Guaranteed Values: MaxSat and MaxCut
• Some optimal inapproximability results
• Digraphs
• Title not available (Why is that?)
• Solving MAX-\(r\)-SAT above a tight lower bound
• The complexity of König subgraph problems and above-guarantee vertex cover
• Vertex packings: Structural properties and algorithms
• On the power of unique 2-prover 1-round games
• Total Ordering Problem
• Kernel bounds for disjoint cycles and disjoint paths
• Étude des coefficients de Fourier des fonctions de \(L^ p(G)\)
• Title not available (Why is that?)
• Crown reductions for the minimum weighted vertex cover problem
• Vertex cover: Further observations and further improvements
• A kernel of order \(2k-c\log k\) for vertex cover
• On the hardness of losing width
• Paths, flowers and vertex cover
• Title not available (Why is that?)
• A kernel of order \(2k - c\) for Vertex Cover
• Minimal unsatisfiable formulas with bounded clause-variable difference are fixed-parameter tractable
• Polynomial-time recognition of minimal unsatisfiable formulas with fixed clause-variable difference.
• Improved parameterized algorithms for above average constraint satisfaction
• Simultaneously satisfying linear equations over \(\mathbb {F}_2\): MaxLin2 and Max-\(r\)-Lin2 parameterized above average
• A new bound for 3-satisfiable MaxSat and its algorithmic application
• Beating the random ordering is hard: every ordering CSP is approximation resistant
• Parameterizing MAX SNP Problems Above Guaranteed Values
• Systems of linear equations over \(\mathbb{F}_2\) and problems parameterized above average
• Complexity of Partial Satisfaction
• Every ternary permutation constraint satisfaction problem parameterized above average has a kernel with a quadratic number of variables
• On the Approximation of Maximum Satisfiability
• A probabilistic approach to problems parameterized above or below tight bounds
• Note on Max Lin-2 above average
• A new approach to cyclic ordering of 2D orientations using ternary relation algebras
• A Geometric Approach to Betweenness
• Complexity of partial satisfaction. II.
• \(\text{Kernel}(s)\) for problems with no kernel: on out-trees with many leaves
• Algorithms with large domination ratio
• On the advantage over a random assignment
• Voting paradoxes and digraphs realizations
• Hypercontractive inequality for pseudo-Boolean functions of bounded Fourier width

Cited In (17)

• Balanced judicious bipartition is fixed-parameter tractable
• Every ternary permutation constraint satisfaction problem parameterized above average has a kernel with a quadratic number of variables
• A Retrospective on (Meta) Kernelization
• A probabilistic approach to problems parameterized above or below tight bounds
• Balanced Judicious Bipartition is Fixed-Parameter Tractable
• A basic parameterized complexity primer
• Parameterized traveling salesman problem: beating the average
• Improved parameterized algorithms for above average constraint satisfaction
• Polynomial kernels for vertex cover parameterized by small degree modulators
• The parameterized complexity of cycle packing: indifference is not an issue
• Solving sparse instances of Max SAT via width reduction and greedy restriction
• Perfect forests in graphs and their extensions
• The complexity of finding (approximate sized) distance-\(d\) dominating set in tournaments
• All ternary permutation constraint satisfaction problems parameterized above average have kernels with quadratic numbers of variables
• Parameterized algorithms for constraint satisfaction problems above average with global cardinality constraints
• Parameterized constraint satisfaction problems: a survey
• Improved exact algorithms for mildly sparse instances of MAX SAT

Uses Software

• LOLIB

This page was built for publication: Constraint Satisfaction Problems Parameterized above or below Tight Bounds: A Survey

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