Detailed Information on Publication Record
2015
Variable-Deletion Backdoors to Planning
KRONEGGER, Martin, Sebastian ORDYNIAK and Andreas PFANDLERBasic 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:
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
Změněno: 13/5/2020 22:48, RNDr. Pavel Šmerk, Ph.D.
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 |
|