onr:"swepub:oai:DiVA.org:liu-102659"
Search: onr:"swepub:oai:DiVA.org:liu-102659" > Parameterized Compl...
- 1 of 1
- Previous record
- Next record
- To hitlist
Parameterized Complexity and Kernel Bounds for Hard Planning Problems
-
- Bäckström, Christer (author)
- Linköpings universitet,Programvara och system,Tekniska högskolan,TCSLAB
-
- Jonsson, Peter (author)
- Linköpings universitet,Programvara och system,Tekniska högskolan,TCSLAB
-
- Ordyniak, Sebastian (author)
- Masaryk University, Brno, Czech Republic
- show more...
- show less...
- (creator_code:org_t)
- Berlin, Heidelberg : Springer Berlin/Heidelberg, 2013
- 2013
- English.
- In: Algorithms and Complexity. - Berlin, Heidelberg : Springer Berlin/Heidelberg. - 9783642382321 - 9783642382338 ; , s. 13-24
- Conference paper (peer-reviewed)
Abstract
Subject headings
Close
- The propositional planning problem is a notoriously difficult computational problem. Downey et al. (1999) initiated the parameterized analysis of planning (with plan length as the parameter) and Bäckström et al. (2012) picked up this line of research and provided an extensive parameterized analysis under various restrictions, leaving open only one stubborn case. We continue this work and provide a full classification. In particular, we show that the case when actions have no preconditions and at most e postconditions is fixed-parameter tractable if e ≤ 2 and W[1]-complete otherwise. We show fixed-parameter tractability by a reduction to a variant of the Steiner Tree problem; this problem has been shown fixed-parameter tractable by Guo et al. (2007). If a problem is fixed-parameter tractable, then it admits a polynomial-time self-reduction to instances whose input size is bounded by a function of the parameter, called the kernel. For some problems, this function is even polynomial which has desirable computational implications. Recent research in parameterized complexity has focused on classifying fixed-parameter tractable problems on whether they admit polynomial kernels or not. We revisit all the previously obtained restrictions of planning that are fixed-parameter tractable and show that none of them admits a polynomial kernel unless the polynomial hierarchy collapses to its third level.
Subject headings
- NATURVETENSKAP -- Data- och informationsvetenskap -- Datavetenskap (hsv//swe)
- NATURAL SCIENCES -- Computer and Information Sciences -- Computer Sciences (hsv//eng)
Publication and Content Type
- ref (subject category)
- kon (subject category)
Find in a library
- Algorithms and Complexity (Search for host publication in LIBRIS)
To the university's database
- 1 of 1
- Previous record
- Next record
- To hitlist
Find more in SwePub
- By the author/editor
- Bäckström, Chris ...
- Jonsson, Peter
- Ordyniak, Sebast ...
- Szeider, Stefan
- About the subject
-
- NATURAL SCIENCES
- NATURAL SCIENCES
- and Computer and Inf ...
- and Computer Science ...
- Articles in the publication
- Algorithms and C ...
- By the university
- Linköping University
Search outside SwePub
- Extend your search to:
- Google Book Search
- Google Scholar
Kungliga biblioteket hanterar dina personuppgifter i enlighet med EU:s dataskyddsförordning (2018), GDPR. Läs mer om hur det funkar här.
Så här hanterar KB dina uppgifter vid användning av denna tjänst.
- Copyright © LIBRIS - National Library Systems
- LIBRIS.kb.se
