D 2017

Combining Treewidth and Backdoors for CSP

GANIAN, Robert, M.S. RAMANUJAN a Stefan SZEIDER

Základní údaje

Originální název

Combining Treewidth and Backdoors for CSP

Autoři

GANIAN, Robert (203 Česká republika, garant, domácí), M.S. RAMANUJAN (356 Indie) a Stefan SZEIDER (40 Rakousko)

Vydání

Nemecko, 34th Symposium on Theoretical Aspects of Computer Science, STACS 2017, March 8-11, 2017, Hannover, Germany, od s. 1-17, 17 s. 2017

Nakladatel

Dagstuhl-LIPIcs

Další údaje

Jazyk

angličtina

Typ výsledku

Stať ve sborníku

Obor

10200 1.2 Computer and information sciences

Stát vydavatele

Německo

Utajení

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

Forma vydání

elektronická verze "online"

Odkazy

Kód RIV

RIV/00216224:14330/17:00100553

Organizační jednotka

Fakulta informatiky

ISBN

978-3-95977-028-6

ISSN

DOI

UT WoS

000521077300036

Klíčová slova anglicky

Treewidth; Backdoors; Constraint Satisfaction

Štítky

Změněno: 28. 4. 2020 12:19, Mgr. Michal Petr

Anotace

V originále

We show that CSP is fixed-parameter tractable when parameterized by the treewidth of a backdoor into any tractable CSP problem over a finite constraint language. This result combines the two prominent approaches for achieving tractability for CSP: (i) structural restrictions on the interaction between the variables and the constraints and (ii) language restrictions on the relations that can be used inside the constraints. Apart from defining the notion of backdoor-treewidth and showing how backdoors of small treewidth can be used to efficiently solve CSP, our main technical contribution is a fixed-parameter algorithm that finds a backdoor of small treewidth.