[Dept. of Computer Science]

Experimentation Project ACS


Title Branch and Bound algorithms for treewidth: Moplex vertices and/or Clique Switching
Student Vacancy
Supervisor Hans Bodlaender
ECTS 7.5 or 15
Related Course(s) Algorithms and Networks
Description In this project, algorithms are studied to compute the treewidth of a given graph exactly, with help of a branch and bound algorithm.

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.
In a 7.5 ECTS size project, one of these two techniques will be evaluated. Also, it will be experimented to use a technique only "sometimes", e.g.,
we could test for moplex vertices only at the first levels of the branch and bound search.

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

Special Note