Document Open Access Logo

Treewidth in Non-Ground Answer Set Solving and Alliance Problems in Graphs

Author Bernhard Bliem

PDF
Thumbnail PDF

File

OASIcs.ICLP.2017.12.pdf
  • Filesize: 477 kB
  • 12 pages

Document Identifiers

Author Details

Bernhard Bliem

Cite As Get BibTex

Bernhard Bliem. Treewidth in Non-Ground Answer Set Solving and Alliance Problems in Graphs. In Technical Communications of the 33rd International Conference on Logic Programming (ICLP 2017). Open Access Series in Informatics (OASIcs), Volume 58, pp. 12:1-12:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/OASIcs.ICLP.2017.12

Abstract

To solve hard problems efficiently via answer set programming (ASP), a promising approach is to take advantage of the fact that real-world instances of many hard problems exhibit small treewidth. Algorithms that exploit this have already been proposed -- however, they suffer from an enormous overhead. In the thesis, we present improvements in the algorithmic methodology for leveraging bounded treewidth that are especially targeted toward problems involving subset minimization. This can be useful for many problems at the second level of the polynomial hierarchy like solving disjunctive ground ASP. Moreover, we define classes of non-ground ASP programs such that grounding such a program together with input facts does not lead to an excessive increase in treewidth of the resulting ground program when compared to the treewidth of the input. This allows ASP users to take advantage of the fact that state-of-the-art ASP solvers perform better on ground programs of small treewidth. Finally, we resolve several open questions on the complexity of alliance problems in graphs. In particular, we settle the long-standing open questions of the complexity of the Secure Set problem and whether the Defensive Alliance problem is fixed-parameter tractable when parameterized by treewidth.

Subject Classification

Keywords
  • answer set programming
  • treewidth
  • secure set
  • defensive alliance
  • parameterized complexity

Metrics

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

References

  1. Michael Abseher, Bernhard Bliem, Günther Charwat, Frederico Dusberger, and Stefan Woltran. Computing secure sets in graphs using answer set programming. J. Logic Comput., 2015. Accepted for publication. URL: http://dx.doi.org/10.1093/logcom/exv060.
  2. Mario Alviano, Carmine Dodaro, Wolfgang Faber, Nicola Leone, and Francesco Ricca. WASP: A native ASP solver based on constraint learning. In Pedro Cabalar and Tran Cao Son, editors, Proceedings of LPNMR 2013, volume 8148 of LNCS, pages 54-66. Springer, 2013. URL: http://dx.doi.org/10.1007/978-3-642-40564-8_6.
  3. Mario Alviano, Carmine Dodaro, Nicola Leone, and Francesco Ricca. Advances in WASP. In Francesco Calimeri, Giovambattista Ianni, and Mirosław Truszczyński, editors, Proceedings of LPNMR 2015, volume 9345 of LNCS, pages 40-54. Springer, 2015. URL: http://dx.doi.org/10.1007/978-3-319-23264-5_5.
  4. Mario Alviano, Wolfgang Faber, Nicola Leone, Simona Perri, Gerald Pfeifer, and Giorgio Terracina. The disjunctive datalog system DLV. In Oege de Moor, Georg Gottlob, Tim Furche, and Andrew Jon Sellers, editors, Revised Selected Papers of Datalog 2010, volume 6702 of LNCS, pages 282-301. Springer, 2011. URL: http://dx.doi.org/10.1007/978-3-642-24206-9_17.
  5. Stefan Arnborg, Jens Lagergren, and Detlef Seese. Easy problems for tree-decomposable graphs. Journal of Algorithms, 12(2):308-340, 1991. URL: http://dx.doi.org/10.1016/0196-6774(91)90006-K.
  6. Bernhard Bliem, Günther Charwat, Markus Hecher, and Stefan Woltran. D-FLAT^2: Subset minimization in dynamic programming on tree decompositions made easy. Fund. Inform., 147(1):27-61, 2016. URL: http://dx.doi.org/10.3233/FI-2016-1397.
  7. Bernhard Bliem, Marius Moldovan, Michael Morak, and Stefan Woltran. The impact of treewidth on ASP grounding and solving. In Carles Sierra and Fahiem Bacchus, editors, Proceedings of IJCAI 2017. The AAAI Press, 2017. Accepted for publication. Google Scholar
  8. Bernhard Bliem and Stefan Woltran. Complexity of secure sets. CoRR, abs/1411.6549, 2014. Updated to version 3 on July 11, 2017. URL: http://arxiv.org/abs/1411.6549.
  9. Bernhard Bliem and Stefan Woltran. Complexity of secure sets. In Ernst W. Mayr, editor, Revised Papers of WG 2015, volume 9224 of LNCS, pages 64-77. Springer, 2016. URL: http://dx.doi.org/10.1007/978-3-662-53174-7_5.
  10. Hans L. Bodlaender. A tourist guide through treewidth. Acta Cybernet., 11(1-2):1-21, 1993. Google Scholar
  11. Hans L. Bodlaender. A linear-time algorithm for finding tree-decompositions of small treewidth. SIAM J. Comput., 25(6):1305-1317, 1996. URL: http://dx.doi.org/10.1137/S0097539793251219.
  12. Gerhard Brewka, Thomas Eiter, and Mirosław Truszczyński. Answer set programming at a glance. Communications of the ACM, 54(12):92-103, 2011. URL: http://dx.doi.org/10.1145/2043174.2043195.
  13. Robert C. Brigham, Ronald D. Dutton, and Stephen T. Hedetniemi. Security in graphs. Discrete Appl. Math., 155(13):1708-1714, 2007. URL: http://dx.doi.org/10.1016/j.dam.2007.03.009.
  14. Francesco Calimeri, Wolfgang Faber, Martin Gebser, Giovambattista Ianni, Roland Kaminski, Thomas Krennwallner, Nicola Leone, Francesco Ricca, and Torsten Schaub. ASP-Core-2 input language format. https://www.mat.unical.it/aspcomp2013/ASPStandardization, 2015. Version: 2.03c.
  15. Bruno Courcelle. The monadic second-order logic of graphs I: Recognizable sets of finite graphs. Inform. and Comput., 85(1):12-75, 1990. URL: http://dx.doi.org/10.1016/0890-5401(90)90043-H.
  16. Bruno Courcelle. The monadic second-order logic of graphs III: Tree-decompositions, minors and complexity issues. RAIRO Theor. Inform. Appl., 26:257-286, 1992. URL: http://dx.doi.org/10.1051/ita/1992260302571.
  17. Marek Cygan, Fedor V. Fomin, Łukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk, and Saket Saurabh. Parameterized Algorithms. Springer International Publishing, Cham, Switzerland, 2015. URL: http://dx.doi.org/10.1007/978-3-319-21275-3.
  18. Rina Dechter. Bucket elimination: A unifying framework for reasoning. Artificial Intelligence, 113(1-2):41-85, 1999. URL: http://dx.doi.org/10.1016/S0004-3702(99)00059-4.
  19. Rina Dechter. Constraint Processing. Elsevier Morgan Kaufmann, Amsterdam, The Netherlands, 2003. URL: http://dx.doi.org/10.1016/b978-1-55860-890-0.x5000-2.
  20. Rodney G. Downey and Michael R. Fellows. Parameterized Complexity. Monographs in Computer Science. Springer, New York, NY, USA, 1999. URL: http://dx.doi.org/10.1007/978-1-4612-0515-9.
  21. Wolfgang Dvořák, Reinhard Pichler, and Stefan Woltran. Towards fixed-parameter tractable algorithms for abstract argumentation. Artificial Intelligence, 186:1-37, 2012. URL: http://dx.doi.org/10.1016/j.artint.2012.03.005.
  22. Thomas Eiter and Georg Gottlob. On the computational cost of disjunctive logic programming: Propositional case. Ann. Math. Artif. Intell., 15(3-4):289-323, 1995. URL: http://dx.doi.org/10.1007/BF01536399.
  23. Islam Elkabani, Enrico Pontelli, and Tran Cao Son. Smodels^A - A system for computing answer sets of logic programs with aggregates. In Chitta Baral, Gianluigi Greco, Nicola Leone, and Giorgio Terracina, editors, Proceedings of LPNMR 2005, volume 3662 of LNCS, pages 427-431. Springer, 2005. URL: http://dx.doi.org/10.1007/11546207_40.
  24. Henning Fernau and Juan A. Rodríguez-Velázquez. A survey on alliances and related parameters in graphs. Electron. J. Graph Theory Appl. (EJGTA), 2(1):70-86, 2014. URL: http://dx.doi.org/10.5614/ejgta.2014.2.1.7.
  25. Johannes Klaus Fichte, Markus Hecher, Michael Morak, and Stefan Woltran. Answer set solving with bounded treewidth revisited. In Marcello Balduccini and Tomi Janhunen, editors, Proceedings of LPNMR 2017, volume 10377 of LNCS, pages 132-145. Springer, 2017. URL: http://dx.doi.org/10.1007/978-3-319-61660-5_13.
  26. Johannes Klaus Fichte and Stefan Szeider. Backdoors to tractable answer set programming. Artificial Intelligence, 220:64-103, 2015. URL: http://dx.doi.org/10.1016/j.artint.2014.12.001.
  27. Gary William Flake, Steve Lawrence, C. Lee Giles, and Frans Coetzee. Self-organization and identification of web communities. IEEE Computer, 35(3):66-71, 2002. URL: http://dx.doi.org/10.1109/2.989932.
  28. Jörg Flum and Martin Grohe. Parameterized Complexity Theory. Texts in Theoretical Computer Science. Springer, 2006. URL: http://dx.doi.org/10.1007/3-540-29953-X.
  29. Martin Gebser, Roland Kaminski, Benjamin Kaufmann, Javier Romero, and Torsten Schaub. Progress in clasp series 3. In Francesco Calimeri, Giovambattista Ianni, and Mirosław Truszczyński, editors, Proceedings of LPNMR 2015, volume 9345 of LNCS, pages 368-383. Springer, 2015. URL: http://dx.doi.org/10.1007/978-3-319-23264-5_31.
  30. Martin Gebser, Roland Kaminski, Benjamin Kaufmann, and Torsten Schaub. Answer Set Solving in Practice. Synthesis Lectures on Artificial Intelligence and Machine Learning. Morgan & Claypool Publishers, Williston, VT, USA, 2012. URL: http://dx.doi.org/10.2200/S00457ED1V01Y201211AIM019.
  31. Martin Gebser, Benjamin Kaufmann, André Neumann, and Torsten Schaub. clasp: A conflict-driven answer set solver. In Chitta Baral, Gerhard Brewka, and John S. Schlipf, editors, Proceedings of LPNMR 2007, volume 4483 of LNCS, pages 260-265. Springer, 2007. URL: http://dx.doi.org/10.1007/978-3-540-72200-7_23.
  32. Martin Gebser, Benjamin Kaufmann, and Torsten Schaub. Conflict-driven answer set solving: From theory to practice. Artificial Intelligence, 187:52-89, 2012. URL: http://dx.doi.org/10.1016/j.artint.2012.04.001.
  33. Michael Gelfond and Vladimir Lifschitz. The stable model semantics for logic programming. In Robert A. Kowalski and Kenneth A. Bowen, editors, Proceedings of JICSLP 1988, volume 2, pages 1070-1080. The MIT Press, 1988. Google Scholar
  34. Georg Gottlob, Reinhard Pichler, and Fang Wei. Bounded treewidth as a key to tractability of knowledge representation and reasoning. Artificial Intelligence, 174(1):105-132, 2010. URL: http://dx.doi.org/10.1016/j.artint.2009.10.003.
  35. Georg Gottlob, Reinhard Pichler, and Fang Wei. Tractable database design and datalog abduction through bounded treewidth. Inf. Syst., 35(3):278-298, 2010. URL: http://dx.doi.org/10.1016/j.is.2009.09.003.
  36. Teresa W. Haynes, Stephen T. Hedetniemi, and Michael A. Henning. Global defensive alliances in graphs. Electron. J. Combin., 10, 2003. URL: http://www.combinatorics.org/Volume_10/Abstracts/v10i1r47.html.
  37. Yiu Yu Ho and Ronald D. Dutton. Rooted secure sets of trees. AKCE Int. J. Graphs Comb., 6(3):373-392, 2009. Google Scholar
  38. Michael Jakl, Reinhard Pichler, Stefan Rümmele, and Stefan Woltran. Fast counting with bounded treewidth. In Iliano Cervesato, Helmut Veith, and Andrei Voronkov, editors, Proceedings of LPAR 2008, volume 5330 of LNCS, pages 436-450. Springer, 2008. URL: http://dx.doi.org/10.1007/978-3-540-89439-1_31.
  39. Michael Jakl, Reinhard Pichler, and Stefan Woltran. Answer-set programming with bounded treewidth. In Craig Boutilier, editor, Proceedings of IJCAI 2009, pages 816-822. The AAAI Press, 2009. Google Scholar
  40. Masashi Kiyomi and Yota Otachi. Alliances in graphs of bounded clique-width. Discrete Appl. Math., 223:91-97, 2017. URL: http://dx.doi.org/10.1016/j.dam.2017.02.004.
  41. András Kornai and Zsolt Tuza. Narrowness, pathwidth, and their application in natural language processing. Discrete Appl. Math., 36(1):87-92, 1992. URL: http://dx.doi.org/10.1016/0166-218X(92)90208-R.
  42. Petter Kristiansen, Sandra M. Hedetniemi, and Stephen T. Hedetniemi. Introduction to alliances in graphs. In Ilyas Cicekli, Nihan Kesim Cicekli, and Erol Gelenbe, editors, Proceedings of ISCIS 2002, pages 308-312. CRC Press, 2002. Google Scholar
  43. Petter Kristiansen, Sandra M. Hedetniemi, and Stephen T. Hedetniemi. Alliances in graphs. J. Combin. Math. Combin. Comput., 48:157-178, 2004. Google Scholar
  44. Nicola Leone, Gerald Pfeifer, Wolfgang Faber, Thomas Eiter, Georg Gottlob, Simona Perri, and Francesco Scarcello. The DLV system for knowledge representation and reasoning. ACM Trans. Comput. Log., 7(3):499-562, 2006. URL: http://dx.doi.org/10.1145/1149114.1149117.
  45. Vladimir Lifschitz. What is answer set programming? In Dieter Fox and Carla P. Gomes, editors, Proceedings of AAAI 2008), pages 1594-1597. The AAAI Press, 2008. Google Scholar
  46. Victor W. Marek and Mirosław Truszczyński. Stable models and an alternative logic programming paradigm. In Krzysztof Apt, Victor W. Marek, Mirosław Truszczyński, and David S. Warren, editors, The Logic Programming Paradigm: A 25-Year Perspective, pages 375-398. Springer, New York, NY, USA, 2011. URL: http://dx.doi.org/10.1007/978-3-642-60085-2.
  47. Michael Morak, Reinhard Pichler, Stefan Rümmele, and Stefan Woltran. A dynamic-programming based ASP-solver. In Tomi Janhunen and Ilkka Niemelä, editors, Proceedings of JELIA 2010, volume 6341 of LNCS, pages 369-372. Springer, 2010. URL: http://dx.doi.org/10.1007/978-3-642-15675-5_34.
  48. Rolf Niedermeier. Invitation to Fixed-Parameter Algorithms, volume 31 of Oxford Lecture Series in Mathematics and its Applications. Oxford University Press, Oxford, United Kingdom, 2006. URL: http://dx.doi.org/10.1093/acprof:oso/9780198566076.001.0001.
  49. Reinhard Pichler, Stefan Rümmele, Stefan Szeider, and Stefan Woltran. Tractable answer-set programming with weight constraints: Bounded treewidth is not enough. Theory Pract. Log. Program., 14(2):141-164, 2014. URL: http://dx.doi.org/10.1017/S1471068412000099.
  50. Neil Robertson and Paul D. Seymour. Graph minors. III. Planar tree-width. J. Combin. Theory Ser. B, 36(1):49-64, 1984. URL: http://dx.doi.org/10.1016/0095-8956(84)90013-3.
  51. Patrik Simons, Ilkka Niemelä, and Timo Soininen. Extending and implementing the stable model semantics. Artificial Intelligence, 138(1-2):181-234, 2002. URL: http://dx.doi.org/10.1016/S0004-3702(02)00187-X.
  52. Mikkel Thorup. All structured programs have small tree-width and good register allocation. Inform. and Comput., 142(2):159-181, 1998. URL: http://dx.doi.org/10.1006/inco.1997.2697.
  53. Ismael González Yero and Juan A. Rodríguez-Velázquez. Defensive alliances in graphs: A survey. CoRR, abs/1308.2096, 2013. URL: http://arxiv.org/abs/1308.2096.
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