#
Monday Lecture and Colloquium

**Monday, October 29, 2012**

Technische Universität Berlin

Institut für Mathematik

Straße des 17. Juni 136

10623 Berlin

room MA 041

** Lecture - 14:15**

### Peter Rossmanith -
RWTH Aachen

### Solving MSO-definable Graph Problems Efficiently

*Abstract:*

Within a graph of bounded treewidth, all MSO-definable
problems can be solved in linear time. Attempts to implement a
corresponding solver using tree automata suffered from state explosion
problems. We present an alternative approach using game trees that
avoids these problems to some degree. Lots of practical problems can
be expressed both as an ILP and by MSO-formulas. If the treewidth of
the underlying graph is not too big, sometimes our tool is able to
outperform commercial ILP solvers.

Joint work with Alexander Langer.

** Colloquium - 16:00 **

### Berit Grußien -
Humboldt-Universität zu Berlin

### Capturing Polynomial Time on Chordal Comparability Graphs

*Abstract:*

The central open problem in descriptive complexity theory is the question of whether there exists a logic that characterizes, or captures, the complexity class PTIME. Recently, it was shown by Grohe that fixed-point logic with counting captures PTIME on all classes of graphs with excluded minors. The question for further interesting graph classes for which we can find a logic capturing PTIME leads us to classes of graphs closed under induced subgraphs.

In my talk I will show that fixed-point logic with counting captures PTIME on chordal comparability graphs. The result is based on a graph decomposition, known as the modular decomposition, which was introduced by Gallai in 1976. It is one of few results for which PTIME is captured on a graph class that is closed under induced subgraphs.

Letzte Aktualisierung:
24.10.2012