[Dept. of Computer Science]

Experimentation Project ACS


Title Preprocessing for Treewidth
Student Vacancy
Supervisor Hans Bodlaender and Eelko Penninkx
ECTS 7.5 or 15
Related Course(s) Algorithms and Networks
Description Preprocessing is almost always a very useful technique when we want to solve hard (e.g., NP-hard) problems.
The treewidth of graphs is a well studied notion and has several applications.

This experimentation project aims at implementing and comparing different preprocessing methods for the problem to compute the treewidth of a given graph.
In the 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 will concentrate on safe separator algorithms. A separator is a set of vertices, that, when removed from the graph, let the graph fall into several components.
Some separators can be used to split the graph in different parts, such that the treewidth problem is equivalent to computing the treewidth of each part.

The project will be done in Java and can be 7.5 or 15 "study points". See also the project on branch-and-bound algorithms for treewidth. It is possible to combine the projects.

References:

  • H.L. Bodlaender, A.M.C.A. Koster, and F. v.d. Eijkhof.
    Pre-processing rules for triangulation of probabilistic networks.
    Computational Intelligence, 21(3):286--305, 2005.
  • H.L. Bodlaender and A.M.C.A. Koster.
    Safe separators for treewidth.
    Disc. Math., 306:337--350, 2006.
  • H.L. Bodlaender and A.M.C.A. Koster.
    Treewidth computations III. Exact algorithms and preprocessing.
    Overview paper in preparation.
  • T. van Dijk, J.-P. v.d. Heuvel, W. Slob. Treewidth.com
Special Note