Combining Treewidth and Backdoors for CSP

Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216224%3A14330%2F17%3A00100553" target="_blank" >RIV/00216224:14330/17:00100553 - isvavai.cz</a>
Result on the web
<a href="http://drops.dagstuhl.de/opus/volltexte/2017/6998/" target="_blank" >http://drops.dagstuhl.de/opus/volltexte/2017/6998/</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.4230/LIPIcs.STACS.2017.36" target="_blank" >10.4230/LIPIcs.STACS.2017.36</a>

Result language
angličtina
Original language name
Combining Treewidth and Backdoors for CSP
Original language description
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.
Czech name
—
Czech description
—

Project
—
Continuities
I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Publication year
2017
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Article name in the collection
34th Symposium on Theoretical Aspects of Computer Science, STACS 2017, March 8-11, 2017, Hannover, Germany
ISBN
9783959770286
ISSN
1868-8969
e-ISSN
—
Number of pages
17
Pages from-to
1-17
Publisher name
Dagstuhl-LIPIcs
Place of publication
Nemecko
Event location
Hannover, Germany
Event date
Jan 1, 2017
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
000521077300036

Similar results(10)