Technical Report MSC-2019-18

Title: Effective Enumeration of Tree Decompositions for Solver Optimization
Authors: Dvir Dukhan
Supervisors: Prof. Benny Kimelfeld
PDFCurrently accessibly only within the Technion network
Abstract: Many problems are efficiently solved on trees or forests, though they are intractable when considering general graphs. In such cases, a tree decomposition of the input graph often facilitates an effective solution. Therefore, tree decompositions are critical for graph problems in the fields of databases, game theory, statistical analysis, bioinformatics, and more. The goal of this research is to build an efficient tool for enumerating (producing) a large space of tree decompositions for solvers of graph problems to select from. While the research is practical, it is relying on recent theoretical development on the complexity of this problem. We have conducted the research in three main steps: First, we have investigated an existing algorithm performance bottlenecks, and considerably optimized them in order to enhance the algorithm overall runtime performance of a single-thread execution. Then, we have devised and developed parallelized versions of the algorithm, each of them taking a different parallelization approach, while retaining the algorithm formal guarantees. Lastly, we evaluated empirically the usability of the different versions of the algorithm, in a recent framework that uses machine learning models in order to learn and evaluate the effectiveness of tree decompositions, when used by a dynamic solver on different graph problems.
CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (, rather than to the URL of the PDF files directly. The latter URLs may change without notice.

To the list of the MSC technical reports of 2019
To the main CS technical reports page

Computer science department, Technion