טכניון מכון טכנולוגי לישראל
הטכניון מכון טכנולוגי לישראל - בית הספר ללימודי מוסמכים  
M.Sc Thesis
M.Sc StudentDukhan Dvir
SubjectEffective Enumeration of Tree Decompositions for Solver
Optimization
DepartmentDepartment of Computer Science
Supervisor Professor Benny Kimelfeld


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.