liu.seSearch for publications in DiVA
Change search
ReferencesLink to record
Permanent link

Direct link
A Refined View of Causal Graphs and Component Sizes: SP-Closed Graph Classes and Beyond
Linköping University, Department of Computer and Information Science, Software and Systems. Linköping University, The Institute of Technology.
Linköping University, Department of Computer and Information Science, Software and Systems. Linköping University, The Institute of Technology.
2013 (English)In: The journal of artificial intelligence research, ISSN 1076-9757, Vol. 47, 575-611 p.Article in journal (Refereed) Published
Abstract [en]

The causal graph of a planning instance is an important tool for planning both in practice and in theory. The theoretical studies of causal graphs have largely analysed the computational complexity of planning for instances where the causal graph has a certain structure, often in combination with other parameters like the domain size of the variables. Chen and Giménez ignored even the structure and considered only the size of the weakly connected components. They proved that planning is tractable if the components are bounded by a constant and otherwise intractable. Their intractability result was, however, conditioned by an assumption from parameterised complexity theory that has no known useful relationship with the standard complexity classes. We approach the same problem from the perspective of standard complexity classes, and prove that planning is NP-hard for classes with unbounded components under an additional restriction we refer to as SP-closed. We then argue that most NP-hardness theorems for causal graphs are difficult to apply and, thus, prove a more general result; even if the component sizes grow slowly and the class is not densely populated with graphs, planning still cannot be tractable unless the polynomial hierachy collapses. Both these results still hold when restricted to the class of acyclic causal graphs. We finally give a partial characterization of the borderline between NP-hard and NP-intermediate classes, giving further insight into the problem.

Place, publisher, year, edition, pages
AAAI Press, 2013. Vol. 47, 575-611 p.
National Category
Engineering and Technology
URN: urn:nbn:se:liu:diva-96717DOI: 10.1613/jair.3968ISI: 000322433700001OAI: diva2:642963
Available from: 2013-08-23 Created: 2013-08-23 Last updated: 2014-11-19

Open Access in DiVA

fulltext(541 kB)133 downloads
File information
File name FULLTEXT01.pdfFile size 541 kBChecksum SHA-512
Type fulltextMimetype application/pdf

Other links

Publisher's full text

Search in DiVA

By author/editor
Bäckström, ChristerJonsson, Peter
By organisation
Software and SystemsThe Institute of Technology
In the same journal
The journal of artificial intelligence research
Engineering and Technology

Search outside of DiVA

GoogleGoogle Scholar
Total: 133 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Altmetric score

Total: 96 hits
ReferencesLink to record
Permanent link

Direct link