[Dept. of Computer Science]

Experimentation Project ACS

Title Local search algorithms for treewidth
Student Henri Kas
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 approximately,
with help of algorithms of "local search type", e.g., simulated annealing or Tabu Search.

We use the LibTW framework, a library with several algorithms to compute or approximate the treewidth which was made in an earlier experimentation project,
and also succesfully used and extended in another experimentation project.

This project aims to extend the framework with heuristic algorithms for treewidth that use
"local search" techniques, e.g., using simulated annealing and/or tabu search.

In a paper "Heuristic and Meta-Heuristic Methods for Computing Graph Treewidth" by Clautiaux et al. (2004), a tabu search algorithm for treewidth was described.
For several test graphs, the results of the tabu search are better than that of any other known implemented algorithm for treewidth.
The tabu search algorithm finds treewidth by looking at permutations of the vertices.
Each permutation has a "width", and the treewidth is the minimum width over all permutations.

In this project, we will experiment with this/and or variants of this method.
Depending on time, a number of the following questions will be investigated:

  • how does tabu search compare to simulated annealing (or other similar methods) using the same cost functions and neighborhood structures?
  • what settings give best results?
  • is the "clique at the end" technique, used with succes in exact treewidth algorithms of use here?
Special Note