Variable-Deletion Backdoors to Planning

D 2015

Variable-Deletion Backdoors to Planning

KRONEGGER, Martin, Sebastian ORDYNIAK and Andreas PFANDLER

Basic information

Original name

Variable-Deletion Backdoors to Planning

Authors

KRONEGGER, Martin (40 Austria), Sebastian ORDYNIAK (276 Germany, belonging to the institution) and Andreas PFANDLER (276 Germany)

Edition

Austin; United States, Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence, p. 3305-3312, 8 pp. 2015

Publisher

AI Access Foundation

Other information

Language

English

Type of outcome

Stať ve sborníku

Field of Study

10201 Computer sciences, information science, bioinformatics

Country of publisher

United States of America

Confidentiality degree

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

Publication form

printed version "print"

References:

URL

RIV identification code

RIV/00216224:14330/15:00087408

Organization unit

Faculty of Informatics

ISBN

978-1-57735-703-2

UT WoS

000485625503049

Keywords in English

Planning; Fixed-parameter tractable algorithms; (Parameterized) complexity theory; Backdoors

Abstract

V originále

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).

Links

EE2.3.30.0009, research and development project

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

Citovat

KRONEGGER, Martin, Sebastian ORDYNIAK and Andreas PFANDLER. Variable-Deletion Backdoors to Planning. In Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence. Austin; United States: AI Access Foundation, 2015, p. 3305-3312. ISBN 978-1-57735-703-2.

@inproceedings{1344311,
   author = {Kronegger, Martin and Ordyniak, Sebastian and Pfandler, Andreas},
   address = {Austin; United States},
   booktitle = {Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence},
   keywords = {Planning; Fixed-parameter tractable algorithms; (Parameterized) complexity theory; Backdoors},
   howpublished = {tištěná verze "print"},
   language = {eng},
   location = {Austin; United States},
   isbn = {978-1-57735-703-2},
   pages = {3305-3312},
   publisher = {AI Access Foundation},
   title = {Variable-Deletion Backdoors to Planning},
   url = {https://www.aaai.org/ocs/index.php/AAAI/AAAI15/paper/view/9885},
   year = {2015}
}

TY  - JOUR
ID  - 1344311
AU  - Kronegger, Martin - Ordyniak, Sebastian - Pfandler, Andreas
PY  - 2015
TI  - Variable-Deletion Backdoors to Planning
PB  - AI Access Foundation
CY  - Austin; United States
SN  - 9781577357032
KW  - Planning
KW  - Fixed-parameter tractable algorithms
KW  - (Parameterized) complexity theory
KW  - Backdoors
UR  - https://www.aaai.org/ocs/index.php/AAAI/AAAI15/paper/view/9885
N2  - 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).
ER  -

KRONEGGER, Martin, Sebastian ORDYNIAK and Andreas PFANDLER. Variable-Deletion Backdoors to Planning. In \textit{Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence}. Austin; United States: AI Access Foundation, 2015, p.~3305-3312. ISBN~978-1-57735-703-2.

Detailed Information on Publication Record