[Dept. of Computer Science]

Experimentation Project ACS

Title Computing Treewidth
Students Thomas van Dijk, Wouter Slob, Jan-Pieter van den Heuvel
Supervisor Hans Bodlaender
ECTS 15 per student
Related Course(s) Algorithms and Networks
Description For several purposes, it is often useful to compute the treewidth of a graph, or to find a tree decomposition with small treewidth.
Results can for example be applied to probabilistic networks and combinatorial optimization problems.

In this project several algorithms for computing the treewidth of graphs are evaluated:

  • Exact algorithms for computing treewidth, e.g. branch-and-bound algoriths, dynamic programming algorithms;
  • Algorithms that provide upper bounds (heuristics for computing treewidth; the minimum degree algorithm, the minimum fill-in algorithm, and variants);
  • Algorithms for finding lower bounds.
In addition, possibly methods for preprocessing of treewidth, and the algorithms for treewidth 1, 2, and/or 3 are considered.

The different algorithms are compared on quality (how good are the solutions compared to optimality), and on their time and possibly memory requirements.
Instances from the TreewidthLib collection are used as test-inputs. The algorithms are implemented as an integrated Java library.