License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/OASIcs.ICLP.2017.12
URN: urn:nbn:de:0030-drops-84656
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/8465/
Go to the corresponding OASIcs Volume Portal

Bliem, Bernhard

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

pdf-format:
OASIcs-ICLP-2017-12.pdf (0.5 MB)

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.

BibTeX - Entry

@InProceedings{bliem:OASIcs:2018:8465,
  author =	{Bernhard Bliem},
  title =	{{Treewidth in Non-Ground Answer Set Solving and Alliance Problems in Graphs}},
  booktitle =	{Technical Communications of the 33rd International Conference on Logic Programming (ICLP 2017)},
  pages =	{12:1--12:12},
  series =	{OpenAccess Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-058-3},
  ISSN =	{2190-6807},
  year =	{2018},
  volume =	{58},
  editor =	{Ricardo Rocha and Tran Cao Son and Christopher Mears and Neda Saeedloei},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/8465},
  URN =		{urn:nbn:de:0030-drops-84656},
  doi =		{10.4230/OASIcs.ICLP.2017.12},
  annote =	{Keywords: answer set programming, treewidth, secure set, defensive alliance, parameterized complexity}
}

Keywords: answer set programming, treewidth, secure set, defensive alliance, parameterized complexity
Collection: Technical Communications of the 33rd International Conference on Logic Programming (ICLP 2017)
Issue Date: 2018
Date of publication: 14.02.2018

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