D 2015

Variable-Deletion Backdoors to Planning

KRONEGGER, Martin, Sebastian ORDYNIAK a Andreas PFANDLER

Základní údaje

Originální název

Variable-Deletion Backdoors to Planning

Autoři

KRONEGGER, Martin (40 Rakousko), Sebastian ORDYNIAK (276 Německo, domácí) a Andreas PFANDLER (276 Německo)

Vydání

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

Nakladatel

AI Access Foundation

Další údaje

Jazyk

angličtina

Typ výsledku

Stať ve sborníku

Obor

10201 Computer sciences, information science, bioinformatics

Stát vydavatele

Spojené státy

Utajení

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

Forma vydání

tištěná verze "print"

Odkazy

Kód RIV

RIV/00216224:14330/15:00087408

Organizační jednotka

Fakulta informatiky

ISBN

978-1-57735-703-2

UT WoS

000485625503049

Klíčová slova anglicky

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

Štítky

Změněno: 13. 5. 2020 22:48, RNDr. Pavel Šmerk, Ph.D.

Anotace

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

Návaznosti

EE2.3.30.0009, projekt VaV
Název: Zaměstnáním čerstvých absolventů doktorského studia k vědecké excelenci