TY - JOUR AU - Kronegger, Martin AU - Ordyniak, Sebastian AU - Pfandler, Andreas PY - 2015/03/04 Y2 - 2024/03/28 TI - Variable-Deletion Backdoors to Planning JF - Proceedings of the AAAI Conference on Artificial Intelligence JA - AAAI VL - 29 IS - 1 SE - Main Track: Planning and Scheduling DO - 10.1609/aaai.v29i1.9662 UR - https://ojs.aaai.org/index.php/AAAI/article/view/9662 SP - AB - <p> 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 variable-deletion 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). </p> ER -