Experimentation Project ACS

We build upon earlier Experimentation Projects. We use the LibTW framework (a library with several algorithms to compute or approximate the treewidth),
and the implementation of a Branch and Bound algorithm in this framework by R. v.d. Beukel.

The branch and bound algorithm computes the treewidth, by looking for a permutation of the vertices with minimum "width".
In the last project, two techniques were evaluated: using a "clique at the end of the permutation" (which gives a large reduction in running time),
and using a "sentinel" technique to quickly detect "simplicial vertices" (when we have a simplicial vertex, we do not have to branch;
this technique however appears not to give significant speedup).

In this project, we will test one or both of the following new, and yet untried techniques to speed up branch and bound algorithms for treewidth:

• "clique switching": while constructing the permutation, edges are added, and new cliques appear.
  It may be sometimes advantageous to change the clique at the end to a larger one.
• selecting only "moplex" vertices: graph theory tells us that we only have to branch on vertices that fulfill a certain property called "moplex".
  This property can be tested with a modification of the depth first search algorithm.

The LibTW library is written in Java, and thus this project also will be done in Java.