Graduiertenkolleg: Methods for Discrete Structures

Deutsche Forschungsgemeinschaft
faculty | junior-faculty | postdocs | students | associate students | former students | former associate students
locations | Term schedule | history
predoc-courses | schools | block-courses | workshops

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

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

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