Document Open Access Logo

Combining Treewidth and Backdoors for CSP

Authors Robert Ganian, M. S. Ramanujan, Stefan Szeider

PDF
Thumbnail PDF

File

LIPIcs.STACS.2017.36.pdf
  • Filesize: 0.68 MB
  • 17 pages

Document Identifiers

Author Details

Robert Ganian
M. S. Ramanujan
Stefan Szeider

Cite As Get BibTex

Robert Ganian, M. S. Ramanujan, and Stefan Szeider. Combining Treewidth and Backdoors for CSP. In 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 66, pp. 36:1-36:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.STACS.2017.36

Abstract

We show that CSP is fixed-parameter tractable when parameterized by the treewidth of a backdoor into any tractable CSP problem over a finite constraint language. This result combines the two prominent approaches for achieving tractability for CSP: (i) structural restrictions on the interaction between the variables and the constraints and (ii) language restrictions on the relations that can be used inside the constraints. Apart from defining the notion of backdoor-treewidth and showing how backdoors of small treewidth can be used to efficiently solve CSP, our main technical contribution is a fixed-parameter algorithm that finds a backdoor of small treewidth.

Subject Classification

Keywords
  • Algorithms and data structures
  • Fixed Parameter Tractability
  • Constraint Satisfaction

Metrics

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

References

  1. Stefan Arnborg, Bruno Courcelle, Andrzej Proskurowski, and Detlef Seese. An algebraic theory of graph reduction. J. ACM, 40(5):1134-1164, 1993. URL: http://dx.doi.org/10.1145/174147.169807.
  2. Christian Bessiere, Clément Carbonnel, Emmanuel Hebrard, George Katsirelos, and Toby Walsh. Detecting and exploiting subproblem tractability. In Francesca Rossi, editor, IJCAI 2013, Proceedings of the 23rd International Joint Conference on Artificial Intelligence, Beijing, China, August 3-9, 2013. IJCAI/AAAI, 2013. Google Scholar
  3. Hans L. Bodlaender and Babette de Fluiter. Reduction algorithms for constructing solutions in graphs with small treewidth. In Jin-Yi Cai and Chak Kuen Wong, editors, COCOON'96, LNCS, pages 199-208. Springer, 1996. Google Scholar
  4. Hans L. Bodlaender and Torben Hagerup. Parallel algorithms with optimal speedup for bounded treewidth. SIAM J. Comput., 27:1725-1746, 1998. Google Scholar
  5. Hans L. Bodlaender and Babette van Antwerpen-de Fluiter. Reduction algorithms for graphs of small treewidth. Inf. Comput., 167:86-119, 2001. Google Scholar
  6. Andrei A. Bulatov. A dichotomy theorem for constraint satisfaction problems on a 3-element set. J. of the ACM, 53(1):66-120, 2006. Google Scholar
  7. Andrei A. Bulatov. Complexity of conservative constraint satisfaction problems. ACM Trans. Comput. Log., 12(4):Art. 24, 66, 2011. Google Scholar
  8. Andrei A. Bulatov. The complexity of the counting constraint satisfaction problem. J. of the ACM, 60(5):Art 34, 41, 2013. Google Scholar
  9. Andrei A. Bulatov, Andrei A. Krokhin, and Peter Jeavons. The complexity of maximal constraint languages. In Jeffrey Scott Vitter, Paul G. Spirakis, and Mihalis Yannakakis, editors, Proceedings on 33rd Annual ACM Symposium on Theory of Computing, July 6-8, 2001, Heraklion, Crete, Greece, pages 667-674. ACM, 2001. Google Scholar
  10. Clément Carbonnel and Martin C. Cooper. Tractability in constraint satisfaction problems: a survey. Constraints, 21(2):115-144, 2016. Google Scholar
  11. Clément Carbonnel, Martin C. Cooper, and Emmanuel Hebrard. On backdoors to tractable constraint languages. In Principles and Practice of Constraint Programming - 20th International Conference, CP 2014, Lyon, France, September 8-12, 2014. Proceedings, volume 8656 of Lecture Notes in Computer Science, pages 224-239. Springer Verlag, 2014. Google Scholar
  12. Rajesh Hemant Chitnis, Marek Cygan, MohammadTaghi Hajiaghayi, Marcin Pilipczuk, and Michal Pilipczuk. Designing FPT algorithms for cut problems using randomized contractions. In 53rd Annual IEEE Symposium on Foundations of Computer Science, FOCS 2012, New Brunswick, NJ, USA, October 20-23, 2012, pages 460-469, 2012. Google Scholar
  13. David Cohen, Peter Jeavons, and Marc Gyssens. A unified theory of structural tractability for constraint satisfaction problems. J. of Computer and System Sciences, 74(5):721-743, 2008. Google Scholar
  14. Martin C. Cooper, David A. Cohen, and Peter G. Jeavons. Characterising tractable constraints. Artificial Intelligence, 65(2):347-361, 1994. Google Scholar
  15. Bruno Courcelle. The monadic second-order logic of graphs. I. recognizable sets of finite graphs. Inf. Comput., 85(1):12-75, 1990. Google Scholar
  16. Y. Crama, O. Ekin, and P. L. Hammer. Variable and term removal from Boolean formulae. Discr. Appl. Math., 75(3):217-230, 1997. Google Scholar
  17. Víctor Dalmau. A new tractable class of constraint satisfaction problems. In AMAI, 6th International Symposium on Artificial Intelligence and Mathematics, Fort Lauderdale, Florida, USA, January 5-7, 2000, 2000. Google Scholar
  18. Víctor Dalmau, Phokion G. Kolaitis, and Moshe Y. Vardi. Constraint satisfaction, bounded treewidth, and finite-variable logics. In Pascal Van Hentenryck, editor, Principles and Practice of Constraint Programming - CP 2002, 8th International Conference, CP 2002, Ithaca, NY, USA, September 9-13, 2002, Proceedings, volume 2470 of Lecture Notes in Computer Science, pages 310-326. Springer Verlag, 2002. Google Scholar
  19. Babette de Fluiter. Algorithms for Graphs of Small Treewidth. PhD thesis, Utrecht University, 1997. Google Scholar
  20. Reinhard Diestel. Graph Theory, 4th Edition, volume 173 of Graduate texts in mathematics. Springer, 2012. Google Scholar
  21. Tommy Färnqvist. Constraint optimization problems and bounded tree-width revisited. In Nicolas Beldiceanu, Narendra Jussien, and Eric Pinson, editors, Integration of AI and OR Techniques in Contraint Programming for Combinatorial Optimzation Problems - 9th International Conference, CPAIOR 2012, Nantes, France, May 28 June1, 2012. Proceedings, volume 7298 of Lecture Notes in Computer Science, pages 163-179. Springer Verlag, 2012. Google Scholar
  22. Tomás Feder and Moshe Y. Vardi. The computational structure of monotone monadic SNP and constraint satisfaction: A study through datalog and group theory. SIAM J. Comput., 28(1):57-104, 1998. Google Scholar
  23. Michael R. Fellows and Michael A. Langston. An analogue of the Myhill-Nerode theorem and its use in computing finite-basis characterizations (extended abstract). In FOCS, pages 520-525, 1989. Google Scholar
  24. Fedor V. Fomin, Daniel Lokshtanov, Neeldhara Misra, M. S. Ramanujan, and Saket Saurabh. Solving d- via backdoors to small treewidth. In Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015, San Diego, CA, USA, January 4-6, 2015, pages 630-641. SIAM, 2015. Google Scholar
  25. Eugene C. Freuder. A sufficient condition for backtrack-bounded search. J. ACM, 32(4):755-761, 1985. Google Scholar
  26. Robert Ganian, M. S. Ramanujan, and Stefan Szeider. Discovering archipelagos of tractability for constraint satisfaction and counting. In Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, Arlington, VA, USA, January 10-12, 2016, pages 1670-1681, 2016. Google Scholar
  27. Serge Gaspers, Neeldhara Misra, Sebastian Ordyniak, Stefan Szeider, and Stanislav Zivny. Backdoors into heterogeneous classes of SAT and CSP. In Carla E. Brodley and Peter Stone, editors, Proceedings of the Twenty-Eighth AAAI Conference on Artificial Intelligence, July 27-31, 2014, Québec City, Québec, Canada., pages 2652-2658. AAAI Press, 2014. Google Scholar
  28. Serge Gaspers, Sebastian Ordyniak, M. S. Ramanujan, Saket Saurabh, and Stefan Szeider. Backdoors to q-horn. Algorithmica, 74(1):540-557, 2016. URL: http://dx.doi.org/10.1007/s00453-014-9958-5.
  29. Serge Gaspers and Stefan Szeider. Strong backdoors to bounded treewidth SAT. In 54th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2013, 26-29 October, 2013, Berkeley, CA, USA, pages 489-498. IEEE Computer Society, 2013. Google Scholar
  30. G. Gottlob, N. Leone, and F. Scarcello. Hypertree decompositions and tractable queries. J. of Computer and System Sciences, 64(3):579-627, 2002. Google Scholar
  31. Martin Grohe. The complexity of homomorphism and constraint satisfaction problems seen from the other side. J. of the ACM, 54(1), 2007. Google Scholar
  32. Martin Grohe, Ken-ichi Kawarabayashi, Dániel Marx, and Paul Wollan. Finding topological subgraphs is fixed-parameter tractable. In Proceedings of the 43rd ACM Symposium on Theory of Computing, STOC 2011, San Jose, CA, USA, 6-8 June 2011, pages 479-488, 2011. Google Scholar
  33. Pavol Hell and Jaroslav Nešetřil. On the complexity of H-coloring. J. Comb. Theory, Ser. B, 48(1):92-110, 1990. Google Scholar
  34. Pavol Hell and Jaroslav Nesetril. Colouring, constraint satisfaction, and complexity. Computer Science Review, 2(3):143-163, 2008. Google Scholar
  35. Lane A. Hemaspaandra and Ryan Williams. SIGACT news complexity theory column 76: an atypical survey of typical-case heuristic algorithms. SIGACT News, pages 70-89, 2012. Google Scholar
  36. Ken-ichi Kawarabayashi and Mikkel Thorup. The minimum k-way cut of bounded size is fixed-parameter tractable. In IEEE 52nd Annual Symposium on Foundations of Computer Science, FOCS 2011, Palm Springs, CA, USA, October 22-25, 2011, pages 160-169, 2011. Google Scholar
  37. Phokion G. Kolaitis. Constraint satisfaction, databases, and logic. In IJCAI-03, Proceedings of the Eighteenth International Joint Conference on Artificial Intelligence, Acapulco, Mexico, August 9-15, 2003, pages 1587-1595. Morgan Kaufmann, 2003. Google Scholar
  38. Phokion G. Kolaitis and Moshe Y. Vardi. Conjunctive-query containment and constraint satisfaction. J. of Computer and System Sciences, 61(2):302-332, 2000. Special issue on the Seventeenth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems (Seattle, WA, 1998). Google Scholar
  39. Jens Lagergren. Upper bounds on the size of obstructions and intertwines. J. Comb. Theory, Ser. B, 73(1):7-40, 1998. Google Scholar
  40. Dániel Marx. Tractable hypergraph properties for constraint satisfaction and conjunctive queries. J. of the ACM, 60(6):Art. 42, 51, 2013. Google Scholar
  41. Ugo Montanari. Networks of constraints: fundamental properties and applications to picture processing. Information Sciences, 7:95-132, 1974. Google Scholar
  42. Naomi Nishimura, Prabhakar Ragde, and Stefan Szeider. Detecting backdoor sets with respect to Horn and binary clauses. In Proceedings of SAT 2004 (Seventh International Conference on Theory and Applications of Satisfiability Testing, 10-13 May, 2004, Vancouver, BC, Canada), pages 96-103, 2004. Google Scholar
  43. Igor Razgon and Barry O'Sullivan. Almost 2-SAT is fixed parameter tractable. J. of Computer and System Sciences, 75(8):435-450, 2009. Google Scholar
  44. Marko Samer and Stefan Szeider. Algorithms for propositional model counting. J. Discrete Algorithms, 8(1):50-64, 2010. Google Scholar
  45. Marko Samer and Stefan Szeider. Constraint satisfaction with bounded treewidth revisited. J. of Computer and System Sciences, 76(2):103-114, 2010. Google Scholar
  46. Thomas J. Schaefer. The complexity of satisfiability problems. In Conference Record of the Tenth Annual ACM Symposium on Theory of Computing (San Diego, Calif., 1978), pages 216-226. ACM, 1978. Google Scholar
  47. Ryan Williams, Carla Gomes, and Bart Selman. Backdoors to typical case complexity. In Georg Gottlob and Toby Walsh, editors, Proceedings of the Eighteenth International Joint Conference on Artificial Intelligence, IJCAI 2003, pages 1173-1178. Morgan Kaufmann, 2003. Google Scholar
  48. Ryan Williams, Carla Gomes, and Bart Selman. On the connections between backdoors, restarts, and heavy-tailedness in combinatorial search. In Informal Proc. of the Sixth International Conference on Theory and Applications of Satisfiability Testing, S. Margherita Ligure - Portofino, Italy, May 5-8, 2003 (SAT 2003), pages 222-230, 2003. 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 About DROPS Imprint Privacy Contact