Computing Tree-Decompositions of Graphs
|
Supervisor |
|
|
Suitable for |
Abstract
Background
It is well known that many otherwise intractable problems become tractable on trees or graphs that are sufficiently "tree-like". The tree-width of a graph measures this "tree-likeness" and graphs of small tree-width are found to be algorithmically well-behaved.
A special feature of graphs of small tree-width is that they can be tree-decomposed into sub-graphs of constant size. However, computing such a tree-decomposition efficiently is a challenge in itself.
Finding a tree-decomposition of small with in a graph is equivalent to finding an ordering of the graph with certain properties. The advantage of this characterisation is that such orderings can be computed using search procedures and backtracking.
Project aims
The aim of this project is to investigate in how far methods borrowed from modern Satisfiability solvers can be used to find such elimination orderings efficiently. Precisely, the aim is to implement an algorithm computing elimination orderings and to experiment with various heuristics and search strategies adopted from SAT solving technology.
Prerequisites
The project is suitable for students with experience in programming in languages such as C/C++ or Java. Prior knowledge of graph theoretical concepts such as elimination orderings or tree-decompositions is not necessary.