Paper Info
Title
Complexity and Approximability of Parameterized MAX-CSPs
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 $${\\text {AND}}$$AND, $${\\text {OR}}$$OR, $${\\text {PARITY}}$$PARITY, and $${\\text {MAJORITY}}$$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 $$\\textsf {FPT}$$FPT time.2.It is [InlineEquation not available: see fulltext.]-hard to compute the exact optimum, but there is a randomized $$\\textsf {FPT}$$FPT approximation scheme ($$\\textsf {FPT\\text {-}AS}$$FPT-AS), which computes a $$(1{-}\\epsilon )$$(1-∈)-approximation in time $$f(k,\\epsilon ) \\cdot {\\text {poly}}(n)$$f(k,∈)·poly(n).3.There is no $$\\textsf {FPT\\text {-}AS}$$FPT-AS unless [InlineEquation not available: see fulltext.]. For the corresponding standard CSPs, we establish $$\\textsf {FPT}$$FPT versus [InlineEquation not available: see fulltext.]-hardness results.
Year
DOI
Venue
2015
10.1007/s00453-017-0310-8
Algorithmica
Keywords
Field
DocType
Constraint satisfaction problems,Parameterized complexity,Approximation,Clique width,Neighborhood diversity
Constraint satisfaction,Discrete mathematics,Graph,Parameterized complexity,Combinatorics,Constraint satisfaction problem,Treewidth,Clique-width,Mathematics
Journal
Volume
Issue
ISSN
79
1
0178-4617
Citations 
PageRank 
References 
0
0.34
23
Authors
5
Name
Order
Citations
PageRank
Holger Dell122016.74
Eun Jung Kim287367.64
Michael Lampis310422.13
Valia Mitsou4407.90
Tobias Mömke519317.86