# Computational Complexity - Research Seminar

## Christian Hoffmann: *Solving Hard Graph Problems Using Tree Decompositions*

June 10, 2008, 10:15 a.m.

E 1 3, Room 415

Many graph problems which are NP-hard in general can be solved in polynomial time if the input is restricted to graphs of bounded tree width. We will introduce the notion of tree decomposition and tree width and give examples of algorithms which use tree decompositions to solve hard problems on graphs of bounded tree width in polynomial time.