License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.IPEC.2015.294
URN: urn:nbn:de:0030-drops-55910
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2015/5591/
Go to the corresponding LIPIcs Volume Portal

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

Complexity and Approximability of Parameterized MAX-CSPs

pdf-format:
28.pdf (0.5 MB)

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. 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 (FPT-AS), which computes a (1-epsilon)-approximation in time f(k,epsilon) * poly(n).
3. There is no FPT-AS unless FPT=W[1].

For the corresponding standard CSPs, we establish FPT vs. W[1]-hardness results.

BibTeX - Entry

@InProceedings{dell_et_al:LIPIcs:2015:5591,
  author =	{Holger Dell and Eun Jung Kim and Michael Lampis and Valia Mitsou and Tobias M{\"o}mke},
  title =	{{Complexity and Approximability of Parameterized MAX-CSPs}},
  booktitle =	{10th International Symposium on Parameterized and Exact Computation (IPEC 2015)},
  pages =	{294--306},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-92-7},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{43},
  editor =	{Thore Husfeldt and Iyad Kanj},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2015/5591},
  URN =		{urn:nbn:de:0030-drops-55910},
  doi =		{10.4230/LIPIcs.IPEC.2015.294},
  annote =	{Keywords: Approximation, Structural Parameters, Constraint Satisfaction}
}

Keywords: Approximation, Structural Parameters, Constraint Satisfaction
Collection: 10th International Symposium on Parameterized and Exact Computation (IPEC 2015)
Issue Date: 2015
Date of publication: 19.11.2015

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI