Parameterized Complexity and Kernel Bounds for Hard Planning Problems
| Autoři | |
|---|---|
| Rok publikování | 2013 |
| Druh | Článek ve sborníku |
| Konference | Lecture Notes in Computer Science |
| Fakulta / Pracoviště MU | |
| Citace | |
| Doi | http://dx.doi.org/10.1007/978-3-642-38233-8_2 |
| Obor | Teorie informace |
| Klíčová slova | bounded planning;parameterized complexity;kernelization |
| Popis | 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. |
| Související projekty: |