Complexity and Approximability of Parameterized MAX-CSPs

DOI10.4230/LIPICS.IPEC.2015.294MaRDI QIDQ5363783zbMATH OpenOpenAlexFDO

Authors Holger Dell, Eun Jung Kim, Michael Lampis, Valia Mitsou, Tobias Mömke

Publication date 29 September 2017

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

zbMATH Keywords

approximationconstraint satisfactionstructural parameters

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Approximation algorithms (68W25)

Abstract: We study the optimization version of constraint satisfaction problems (Max-CSPs) in the framework of parameterized complexity; the goal is to compute the maximum fraction of constraints that can be satisfied simultaneously. In standard CSPs, we want to decide whether this fraction equals one. The parameters we investigate are structural measures, such as the treewidth or the clique-width of the variable-constraint incidence graph of the CSP instance. We consider Max-CSPs with the constraint types AND, OR, PARITY, and MAJORITY, and with various parameters k, and we attempt to fully classify them into the following three cases: 1. The exact optimum can be computed in FPT time. 2. It is W[1]-hard to compute the exact optimum, but there is a randomized FPT approximation scheme (FPTAS), which computes a $(1-epsilon)$-approximation in time $f(k,epsilon)cdotpoly(n)$. 3. There is no FPTAS unless FPT=W[1]. For the corresponding standard CSPs, we establish FPT vs. W[1]-hardness results.

Recommendations

• Complexity and approximability of parameterized MAX-CSPs
• The Parameterized Complexity of Maximality and Minimality Problems
• The parameterized complexity of maximality and minimality problems
• The approximability of MAX CSP with fixed-value constraints
• scientific article; zbMATH DE number 1258327
• scientific article; zbMATH DE number 1552232
• Parameterized complexity of constraint satisfaction problems
• scientific article; zbMATH DE number 1002206
• Approximation algorithms for the maximum satisfiability problem

Cited in

(13)

• On parameterized complexity of the multi-MCS problem
• Uniform CSP parameterized by solution size is in W[1]
• Complexity and approximability of parameterized MAX-CSPs
• The parameterized complexity of maximality and minimality problems
• On the parameterized complexity of the Maximum Exposure Problem
• Parameterized compilation lower bounds for restricted CNF-formulas
• Complexity of approximating CSP with balance / hard constraints
• A general reduction theorem with applications to pathwidth and the complexity of Max 2-CSP
• Treewidth with a quantifier alternation revisited
• The Worst Case Complexity of Maximum Parsimony
• Treewidth-pliability and PTAS for Max-CSPs
• Parameterized complexity of constraint satisfaction problems
• Complexity of problem \(TF2|v=1,c=2|C_{\max}\)

This page was built for publication: Complexity and Approximability of Parameterized MAX-CSPs

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