Parameterized Complexity and Kernel Bounds for Hard Planning
Problems

D 2013

Parameterized Complexity and Kernel Bounds for Hard Planning Problems

BACKSTROEM, Christer, Peter JONSSON, Sebastian ORDYNIAK a Stefan SZEIDER

Základní údaje

Originální název

Parameterized Complexity and Kernel Bounds for Hard Planning Problems

Autoři

BACKSTROEM, Christer (752 Švédsko), Peter JONSSON (752 Švédsko), Sebastian ORDYNIAK (276 Německo, garant, domácí) a Stefan SZEIDER (40 Rakousko)

Vydání

Germany, Lecture Notes in Computer Science, od s. 13-24, 12 s. 2013

Nakladatel

Springer

Další údaje

Jazyk

angličtina

Typ výsledku

Stať ve sborníku

Obor

10000 1. Natural Sciences

Stát vydavatele

Německo

Utajení

není předmětem státního či obchodního tajemství

Forma vydání

tištěná verze "print"

Impakt faktor

Impact factor: 0.402 v roce 2005

Kód RIV

RIV/00216224:14330/13:00072819

Organizační jednotka

Fakulta informatiky

ISBN

978-3-642-38232-1

ISSN

DOI

http://dx.doi.org/10.1007/978-3-642-38233-8_2

Klíčová slova anglicky

bounded planning;parameterized complexity;kernelization

Příznaky

Mezinárodní význam, Recenzováno

Změněno: 24. 4. 2014 19:26, RNDr. Pavel Šmerk, Ph.D.

Anotace

V originále

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.

Návaznosti

EE2.3.30.0009, projekt VaV

Název: Zaměstnáním čerstvých absolventů doktorského studia k vědecké excelenci

Citovat

BACKSTROEM, Christer, Peter JONSSON, Sebastian ORDYNIAK a Stefan SZEIDER. Parameterized Complexity and Kernel Bounds for Hard Planning Problems. In Paul G. Spirakis, Maria J. Serna. Lecture Notes in Computer Science. Germany: Springer, 2013, s. 13-24. ISBN 978-3-642-38232-1. Dostupné z: https://dx.doi.org/10.1007/978-3-642-38233-8_2.

@inproceedings{1173834,
   author = {Backstroem, Christer and Jonsson, Peter and Ordyniak, Sebastian and Szeider, Stefan},
   address = {Germany},
   booktitle = {Lecture Notes in Computer Science},
   doi = {http://dx.doi.org/10.1007/978-3-642-38233-8_2},
   editor = {Paul G. Spirakis, Maria J. Serna},
   keywords = {bounded planning;parameterized complexity;kernelization},
   howpublished = {tištěná verze "print"},
   language = {eng},
   location = {Germany},
   isbn = {978-3-642-38232-1},
   pages = {13-24},
   publisher = {Springer},
   title = {Parameterized Complexity and Kernel Bounds for Hard Planning Problems},
   year = {2013}
}

TY  - JOUR
ID  - 1173834
AU  - Backstroem, Christer - Jonsson, Peter - Ordyniak, Sebastian - Szeider, Stefan
PY  - 2013
TI  - Parameterized Complexity and Kernel Bounds for Hard Planning Problems
PB  - Springer
CY  - Germany
SN  - 9783642382321
KW  - bounded planning;parameterized complexity;kernelization
N2  - 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.
ER  -

BACKSTROEM, Christer, Peter JONSSON, Sebastian ORDYNIAK a Stefan SZEIDER. Parameterized Complexity and Kernel Bounds for Hard Planning Problems. In Paul G. Spirakis, Maria J. Serna. \textit{Lecture Notes in Computer Science}. Germany: Springer, 2013, s.~13-24. ISBN~978-3-642-38232-1. Dostupné z: https://dx.doi.org/10.1007/978-3-642-38233-8\_{}2.

Podrobný výpis o publikaci