[Dept. of Computer Science]

Experimentation Project ACS

Title Branch and Bound Algorithms for Treewidth
Student Ruud van den Beukel
Supervisor Hans Bodlaender
ECTS 7.5
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.
The treewidth of graphs is a well studied notion and has several applications. In this project, we build upon the LibTW framework
(a library with several algorithms to compute or approximate the treewidth) constructed in a previous experimentation project.

The project looks at an algorithm, proposed by Gogate and Dechter, and by Bachoore and Bodlaender,
where treewidth is represented as a problem to find a permutation of the vertices with minimum "width".

In this project, a number of techniques will be tried out to speed up such branch and bound algorithms.
A selection will be made of the following techniques:

  • the effect of singling out a clique to appear at the end of the permutation
  • fast implementations of tests for simplicial or almost simplicial vertices
  • different methods to restore information when going "up in recursion" ("copy or set back")
  • selecting only so called "moplex" vertices
  • making the fill-in explicitly, or using the implicit representation of fill-in by the set of eliminated vertices
Due to the size of the project, it is expected that only a subset of these techniques can be implemented and tested.
Special Note