The Taub Faculty of Computer Science Events and Talks

Many intractable computational problems on graphs admit tractable algorithms when applied to trees or forests. 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 a recent theoretical development on the complexity of this problem. We have conducted the research in three main steps: First, we have investigated and improved an existing algorithm in order to enhance its runtime performance of a single-thread execution. Then, we have developed parallelized versions of the algorithm, while retaining its formal guarantees. Lastly, we tested the usability of the algorithm in a recent framework that learns the effectiveness of a tree decomposition on different graph problems.