Parameterized Complexity and Kernel Bounds for Hard Planning Problems

Investor logo

Warning

This publication doesn't include Faculty of Sports Studies. It includes Faculty of Informatics. Official publication website can be found on muni.cz.
Authors

BACKSTROEM Christer JONSSON Peter ORDYNIAK Sebastian SZEIDER Stefan

Year of publication 2013
Type Article in Proceedings
Conference Lecture Notes in Computer Science
MU Faculty or unit

Faculty of Informatics

Citation
Doi http://dx.doi.org/10.1007/978-3-642-38233-8_2
Field Information theory
Keywords bounded planning;parameterized complexity;kernelization
Description The propositional planning problem is a notoriously difficult computational problem. Downey, Fellows and Stege initiated the parameterized analysis of planning (with plan length as the parameter) and B\"{a}ckstr\"{o}m et al. 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\leq 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 recently been shown fixed-parameter tractable by Guo, Niedermeier and Suchy. 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.
Related projects:

You are running an old browser version. We recommend updating your browser to its latest version.

More info