This project is an implementation of the reinterpretation of Tamaki's algorithm for calculating treewidths presented in our paper On Tamaki’s Algorithm to Compute Treewidths.
Given an input graph, it calculates the treewidth and outputs a minimal tree decomposition (also called junction tree or clique tree). They are useful as an intermediate step in a number of graph applications. Besides well-known NP-hard graph problems like Clique, Travelling Salesman, and Hamiltonian Circuit, these include probabilistic inference algorithms on Bayesian networks or Markov random fields as well as matrix decompositions. Tamaki's implementation can be found here.
Build the solution and run
Tamaki_Tree_Decomp.exe <path to graph file>.
The program expects a .gr file and outputs the tree decomposition to the command line in the form of a .td file. The .gr and .td file formats are described in detail on the website for the PACE 2017 challenge.