Bounded treewidth as a key to tractability of knowledge representation and reasoning

Journal article

Several forms of reasoning in AI – like abduction, closed world reasoning, circumscription, and disjunctive logic programming – are well known to be intractable. In fact, many of the relevant problems are on the second or third level of the polynomial hierarchy. In this paper, we show how the notion of treewidth can be fruitfully applied to this area. In particular, we show that all these problems become tractable (actually, even solvable in linear time), if the treewidth of the involved formulae or programs is bounded by some constant.

Clearly, these theoretical tractability results as such do not immediately yield feasible algorithms. However, we have recently established a new method based on monadic datalog which allowed us to design an efficient algorithm for a related problem in the database area. In this work, we exploit the monadic datalog approach to construct new algorithms for logic-based abduction.

Authors: Gottlob, G; Pichler, R; Wei, F

• Publication status: Published
• Peer review status: Peer reviewed
• Publisher: Elsevier
• Journal: Artificial Intelligence
• Volume: 174
• Issue: 1
• Pages: 105–132
• Publication date: 2010-01-01
• Edition: Publisher's version
• DOI: 10.1016/j.artint.2009.10.003
• ISSN: 0004-3702
• Language: English
• Keywords: Monadic datalog; Closed world reasoning; Disjunctive logic programming; Treewidth; Fixed-parameter tractability; Abduction
• Subjects: Applications and algorithms