Graduiertenkolleg: Methods for Discrete Structures

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.

• entire schedule WS 2012/13