[Back]

J. Fichte, N. Lodha, S. Szeider:
"SAT-Based Local Improvement for Finding Tree Decompositions of Small Width";
Talk: 20th International Conference on Theory and Applications of Satisfiability Testing - SAT 2017, Melbourne, Australien; 2017-08-28 - 2017-09-01; in: "Proceedings on the 20th International Conference on Theory and Applications of Satisfiability Testing - {SAT} 2017 - 20th International Conference, Melbourne, VIC, Australia, August 28 - September 1, 2017.", S. Gaspers, T. Walsh (ed.); Lecture Notes in Computer Science (LNCS) / Springer, 10491 (2017), ISBN: 978-3-319-66263-3; 401 - 411.

Many hard problems can be solved efficiently for problem instances that can be decomposed by tree decompositions of small width. In particular for problems beyond NP, such as {\#}P-complete counting problems, tree decomposition-based methods are particularly attractive. However, finding an optimal tree decomposition is itself an NP-hard problem. Existing methods for finding tree decompositions of small width either (a) yield optimal tree decompositions but are applicable only to small instances or (b) are based on greedy heuristics which often yield tree decompositions that are far from optimal. In this paper, we propose a new method that combines (a) and (b), where a heuristically obtained tree decomposition is improved locally by means of a SAT encoding. We provide an experimental evaluation of our new method

SAT-Based;Local; Improvement; Finding;Tree; Decompositions;Small; Width;

http://dx.doi.org/10.1007/978-3-319-66263-3_25