Variable-Deletion Backdoors to Planning

Logo poskytovatele

Varování

Publikace nespadá pod Filozofickou fakultu, ale pod Fakultu informatiky. Oficiální stránka publikace je na webu muni.cz.
Autoři

KRONEGGER Martin ORDYNIAK Sebastian PFANDLER Andreas

Rok publikování 2015
Druh Článek ve sborníku
Konference Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence
Fakulta / Pracoviště MU

Fakulta informatiky

Citace
www https://www.aaai.org/ocs/index.php/AAAI/AAAI15/paper/view/9885
Obor Informatika
Klíčová slova Planning; Fixed-parameter tractable algorithms; (Parameterized) complexity theory; Backdoors
Popis Backdoors are a powerful tool to obtain efficient algorithms for hard problems. Recently, two new notions of backdoors to planning were introduced. However, for one of the new notions (i.e., variable-deletion) only hardness results are known so far. In this work we improve the situation by defining a new type of variabledeletion backdoors based on the extended causal graph of a planning instance. For this notion of backdoors several fixed-parameter tractable algorithms are identified. Furthermore, we explore the capabilities of polynomial time preprocessing, i.e., we check whether there exists a polynomial kernel. Our results also show the close connection between planning and verification problems such as Vector Addition System with States (VASS).
Související projekty:

Používáte starou verzi internetového prohlížeče. Doporučujeme aktualizovat Váš prohlížeč na nejnovější verzi.