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

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
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, E-ISSN 1943-5037, 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
Identifiers
URN: urn:nbn:se:liu:diva-96717DOI: 10.1613/jair.3968ISI: 000322433700001OAI: oai:DiVA.org:liu-96717DiVA: diva2:642963
Available from: 2013-08-23 Created: 2013-08-23 Last updated: 2017-12-06

Open Access in DiVA

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

Other links

Publisher's full text

Authority records BETA

Bäckström, ChristerJonsson, Peter

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: 166 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

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 119 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf