Document Open Access Logo

Complexity and Approximability of Parameterized MAX-CSPs

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

PDF
Thumbnail PDF

File

LIPIcs.IPEC.2015.294.pdf
  • Filesize: 0.5 MB
  • 13 pages

Document Identifiers

Author Details

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

Cite AsGet BibTex

Holger Dell, Eun Jung Kim, Michael Lampis, Valia Mitsou, and Tobias Mömke. Complexity and Approximability of Parameterized MAX-CSPs. In 10th International Symposium on Parameterized and Exact Computation (IPEC 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 43, pp. 294-306, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)
https://doi.org/10.4230/LIPIcs.IPEC.2015.294

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.
Keywords
  • Approximation
  • Structural Parameters
  • Constraint Satisfaction

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Michael Alekhnovich and Alexander A. Razborov. Satisfiability, branch-width and Tseitin tautologies. Computational Complexity, 20(4):649-678, 2011. Google Scholar
  2. Per Austrin and Subhash Khot. A characterization of approximation resistance for even k-partite csps. In Robert D. Kleinberg, editor, Innovations in Theoretical Computer Science, ITCS'13, Berkeley, CA, USA, January 9-12, 2013, pages 187-196. ACM, 2013. Google Scholar
  3. Bruno Courcelle, Johann A. Makowsky, and Udi Rotics. Linear time solvable optimization problems on graphs of bounded clique-width. Theory Comput. Syst., 33(2):125-150, 2000. Google Scholar
  4. Nadia Creignou. A dichotomy theorem for maximum generalized satisfiability problems. Journal of Computer and System Sciences, 51(3):511-522, 1995. Google Scholar
  5. Rodney G. Downey and Michael R. Fellows. Fundamentals of Parameterized Complexity. Texts in Computer Science. Springer, 2013. Google Scholar
  6. Serge Gaspers and Stefan Szeider. Kernels for global constraints. In Toby Walsh, editor, IJCAI 2011, Proceedings of the 22nd International Joint Conference on Artificial Intelligence, Barcelona, Catalonia, Spain, July 16-22, 2011, pages 540-545. IJCAI/AAAI, 2011. Google Scholar
  7. Serge Gaspers and Stefan Szeider. Backdoors to acyclic SAT. In Artur Czumaj, Kurt Mehlhorn, Andrew M. Pitts, and Roger Wattenhofer, editors, Automata, Languages, and Programming - 39th International Colloquium, ICALP 2012, Warwick, UK, July 9-13, 2012, Proceedings, Part I, volume 7391 of Lecture Notes in Computer Science, pages 363-374. Springer, 2012. Google Scholar
  8. Serge Gaspers and Stefan Szeider. Guarantees and limits of preprocessing in constraint satisfaction and reasoning. Artif. Intell., 216:1-19, 2014. Google Scholar
  9. Martin Grohe. The structure of tractable constraint satisfaction problems. In Rastislav Kralovic and Pawel Urzyczyn, editors, MFCS 2006, Stará Lesná, Slovakia, August 28-September 1, 2006, Proceedings, volume 4162 of Lecture Notes in Computer Science, pages 58-72. Springer, 2006. Google Scholar
  10. Frank Gurski and Egon Wanke. The tree-width of clique-width bounded graphs without K_n, n. In Ulrik Brandes and Dorothea Wagner, editors, Graph-Theoretic Concepts in Computer Science, 26th International Workshop, WG 2000, Konstanz, Germany, June 15-17, 2000, Proceedings, volume 1928 of Lecture Notes in Computer Science, pages 196-205. Springer, 2000. Google Scholar
  11. Johan Håstad. Some optimal inapproximability results. J. ACM, 48(4):798-859, 2001. Google Scholar
  12. Sanjeev Khanna, Madhu Sudan, and David P. Williamson. A complete classification of the approximability of maximization problems derived from boolean constraint satisfaction. In Frank Thomson Leighton and Peter W. Shor, editors, Proceedings of the Twenty-Ninth Annual ACM Symposium on the Theory of Computing, El Paso, Texas, USA, May 4-6, 1997, pages 11-20. ACM, 1997. Google Scholar
  13. Subhash Khot and Rishi Saket. Approximating csps using LP relaxation. In Magnús M. Halldórsson, Kazuo Iwama, Naoki Kobayashi, and Bettina Speckmann, editors, Automata, Languages, and Programming - 42nd International Colloquium, ICALP 2015, Kyoto, Japan, July 6-10, 2015, Proceedings, Part I, volume 9134 of Lecture Notes in Computer Science, pages 822-833. Springer, 2015. Google Scholar
  14. Michael Lampis. Algorithmic meta-theorems for restrictions of treewidth. Algorithmica, 64(1):19-37, 2012. Google Scholar
  15. Dániel Marx. Parameterized complexity and approximation algorithms. Comput. J., 51(1):60-78, 2008. Google Scholar
  16. Sebastian Ordyniak, Daniël Paulusma, and Stefan Szeider. Satisfiability of acyclic and almost acyclic CNF formulas. Theor. Comput. Sci., 481:85-99, 2013. Google Scholar
  17. Daniël Paulusma, Friedrich Slivovsky, and Stefan Szeider. Model counting for CNF formulas of bounded modular treewidth. In Natacha Portier and Thomas Wilke, editors, STACS 2013, February 27 - March 2, 2013, Kiel, Germany, volume 20 of LIPIcs, pages 55-66. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2013. Google Scholar
  18. Reinhard Pichler, Stefan Rümmele, Stefan Szeider, and Stefan Woltran. Tractable answer-set programming with weight constraints: bounded treewidth is not enough. TPLP, 14(2):141-164, 2014. Google Scholar
  19. Sigve Hortemo Sæther, Jan Arne Telle, and Martin Vatshelle. Solving maxsat and #sat on structured CNF formulas. In Carsten Sinz and Uwe Egly, editors, SAT 2014 - Vienna, Austria, July 14-17, 2014. Proceedings, volume 8561 of Lecture Notes in Computer Science, pages 16-31. Springer, 2014. Google Scholar
  20. Marko Samer and Stefan Szeider. Constraint satisfaction with bounded treewidth revisited. J. Comput. Syst. Sci., 76(2):103-114, 2010. Google Scholar
  21. Thomas J. Schaefer. The complexity of satisfiability problems. In Richard J. Lipton, Walter A. Burkhard, Walter J. Savitch, Emily P. Friedman, and Alfred V. Aho, editors, Proceedings of the 10th Annual ACM Symposium on Theory of Computing, May 1-3, 1978, San Diego, California, USA, pages 216-226. ACM, 1978. Google Scholar
  22. Friedrich Slivovsky and Stefan Szeider. Model counting for formulas of bounded clique-width. In Leizhen Cai, Siu-Wing Cheng, and Tak Wah Lam, editors, ISAAC 2013, Hong Kong, China, Proceedings, volume 8283 of Lecture Notes in Computer Science, pages 677-687. Springer, 2013. Google Scholar
  23. Stefan Szeider. On fixed-parameter tractable parameterizations of SAT. In Enrico Giunchiglia and Armando Tacchella, editors, Theory and Applications of Satisfiability Testing, 6th International Conference, SAT 2003. Santa Margherita Ligure, Italy, May 5-8, 2003 Selected Revised Papers, volume 2919 of Lecture Notes in Computer Science, pages 188-202. Springer, 2003. Google Scholar
  24. Stefan Szeider. Not so easy problems for tree decomposable graphs. CoRR, abs/1107.1177, 2011. Google Scholar
  25. Stefan Szeider. The parameterized complexity of constraint satisfaction and reasoning. In Hans Tompits, Salvador Abreu, Johannes Oetsch, Jörg Pührer, Dietmar Seipel, Masanobu Umeda, and Armin Wolf, editors, INAP 2011, and WLP 2011, Vienna, Austria, September 28-30, 2011, Revised Selected Papers, volume 7773 of Lecture Notes in Computer Science, pages 27-37. Springer, 2011. Google Scholar
  26. Stefan Szeider. The parameterized complexity of k-flip local search for SAT and MAX SAT. Discrete Optimization, 8(1):139-145, 2011. Google Scholar
  27. Luca Trevisan. Inapproximability of combinatorial optimization problems. Electronic Colloquium on Computational Complexity (ECCC), 2004. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact