Variable-Deletion Backdoors to Planning
| Autoři | |
|---|---|
| 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 | |
| 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: |