Ganian, R., Ramanujan, M. S., & Szeider, S. (2017). Combining Treewidth and Backdoors for CSP. In H. Vollmer & B. Vallée (Eds.), 34th Symposium on Theoretical Aspects of Computer Science (pp. 429–445). Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Germany. https://doi.org/10.4230/LIPIcs.STACS.2017.36
E192-01 - Forschungsbereich Algorithms and Complexity
-
Published in:
34th Symposium on Theoretical Aspects of Computer Science
-
ISBN:
978-3-95977-028-6
-
Volume:
66
-
Date (published):
2017
-
Event name:
34th International Symposium on Theoretical Aspects of Computer Science
en
Event date:
8-Mar-2017 - 11-Mar-2017
-
Event place:
Hannover, Germany
-
Number of Pages:
17
-
Publisher:
Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Germany, Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik
-
Publisher:
Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, Dagstuhl
-
Keywords:
Constraint Satisfaction; Algorithms and data structures; Fixed Parameter Tractability
-
Abstract:
Decomposition width parameters such as treewidth provide a measurement
on the complexity of a graph. Finding a decomposition of smallest
width is itself NP-hard but lends itself to a SAT-based
solution. Previous work on treewidth, branchwidth and clique-width
indicates that identifying a suitable characterization of the
considered decomposition method is key for a practically feasible
SAT-encoding. In this paper we study SAT-encodings for the
decomposition width parameters special treewidth and pathwidth. In
both cases we develop SAT-encodings based on two different
characterizations. In particular, we develop two novel
characterizations for special treewidth based on parti- tions and
elimination orderings. We empirically obtained SAT-encodings.
