GANIAN, Robert, M.S. RAMANUJAN and Stefan SZEIDER. Combining Treewidth and Backdoors for CSP. Online. In Heribert Vollmer and Brigitte Vallee. 34th Symposium on Theoretical Aspects of Computer Science, STACS 2017, March 8-11, 2017, Hannover, Germany. Nemecko: Dagstuhl-LIPIcs, 2017, p. 1-17. ISBN 978-3-95977-028-6. Available from: https://dx.doi.org/10.4230/LIPIcs.STACS.2017.36.
Other formats:   BibTeX LaTeX RIS
Basic information
Original name Combining Treewidth and Backdoors for CSP
Authors GANIAN, Robert (203 Czech Republic, guarantor, belonging to the institution), M.S. RAMANUJAN (356 India) and Stefan SZEIDER (40 Austria).
Edition Nemecko, 34th Symposium on Theoretical Aspects of Computer Science, STACS 2017, March 8-11, 2017, Hannover, Germany, p. 1-17, 17 pp. 2017.
Publisher Dagstuhl-LIPIcs
Other information
Original language English
Type of outcome Proceedings paper
Field of Study 10200 1.2 Computer and information sciences
Country of publisher Germany
Confidentiality degree is not subject to a state or trade secret
Publication form electronic version available online
WWW URL
RIV identification code RIV/00216224:14330/17:00100553
Organization unit Faculty of Informatics
ISBN 978-3-95977-028-6
ISSN 1868-8969
Doi http://dx.doi.org/10.4230/LIPIcs.STACS.2017.36
UT WoS 000521077300036
Keywords in English Treewidth; Backdoors; Constraint Satisfaction
Tags firank_A
Changed by Changed by: Mgr. Michal Petr, učo 65024. Changed: 28/4/2020 12:19.
Abstract
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.
PrintDisplayed: 30/4/2024 18:39