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. p. 3305-3312. ISBN 978-1-57735-703-2. 2015.
Other formats:   BibTeX LaTeX RIS
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
Original language English
Type of outcome Proceedings paper
Field of Study 10201 Computer sciences, information science, bioinformatics
Country of publisher United States of America
Confidentiality degree is not subject to a state or trade secret
Publication form printed version "print"
WWW 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
Tags core_A, firank_1
Changed by Changed by: RNDr. Pavel Šmerk, Ph.D., učo 3880. Changed: 13/5/2020 22:48.
Abstract
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 projectName: Zaměstnáním čerstvých absolventů doktorského studia k vědecké excelenci
PrintDisplayed: 29/3/2024 08:16