#
Monday Lecture and Colloquium

**Monday, December 10, 2012**

Technische Universität Berlin

Institut für Mathematik

Straße des 17. Juni 136

10627 Berlin

room MA 041

** Lecture - 14:15**

###
Stefan Kratsch - Technische Universität Berlin

### Parameterized complexity results for treewidth

*Abstract:*

The notion of treewidth plays an important role in theoretical and practical studies of NP-hard graph problems. It is well known that many problems can be solved efficiently on graphs of bounded treewidth. This is supported by Bodlaender's Theorem (constructive testing for bounded treewidth in linear time) and Courcelle's Meta-Theorem (any graph property definable in monadic second order logic can be decided in linear time on graphs of bounded treewidth). However, since both results involve a substantial exponential dependence on the treewidth, there is strong demand for two things: approximate or heuristic algorithms for finding good tree decompositions, and faster tailor-made dynamic programming formulations for specific problems.

The lecture will recall the relevant definitions and then present parameterized complexity results for both mentioned aspects: In the first part, we will consider some well-known reduction rules for the problem of finding a tree decomposition, and show that we can get provable upper bounds on reduced instances (with respect to appropriate parameters). In the second part, we will give some basic intuition for solving connectivity problems, like Traveling Salesman, by dynamic programming on a tree decomposition, and then show how to improve over the naive approach by using linear algebra.

**Colloquium - 16:00**

###
Kostas Stavropoulos - Humboldt-Universität zu Berlin

###
Relating the minor-minimal obstructions for Vertex Cover and
Feedback Vertex Set

*Abstract:*

One of the immediate consequences of the Graph Minors Theorem by
Robertson and Seymour, previously known as Wagner's conjecture, is that a
family of graphs closed under taking minors can be completely
characterised by excluding a finite set of forbidden minor-minimal graphs,
also called obstructions. However, in order to constructively test if a
given graph is a member of such a family, it is necessary to have full
knowledge of these forbidden minors. We discuss some relations between the
respective obstructions for Vertex Cover and Feedback Vertex Set.