Monday, October 29, 2012
Technische Universität Berlin
Institut für Mathematik
Straße des 17. Juni 136
room MA 041
Lecture - 14:15
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
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.