Monday, June 4, 2007
Technische Universität Berlin
Fak. II, Institut für Mathematik
Str. des 17. Juni 136
room MA 041
Lecture - 14:15
In a series running up to currently 23 papers, Robertson and Seymour developed their groundbreaking graph minor theory, culminating in the proof of Wagner's conjecture that in every infinite set of finite graphs, one is a minor of another.
Many parts of this theory have found algorithmic applications - perhaps the notion of tree-width being the most prominent. But also other parts of the theory are used in the design of algorithms. In particular, strong decomposition theorems exploiting the structure of graphs with excluded minors have been used to design explicit algorithms for various problems on graphs excluding a fixed minor.
Logical approaches to algorithms and graph minors study ways of describing algorithmic problems in a logical formalism. For instance, many natural problems on graphs can be formalised in first-order logic or extensions of it. Results in this area are of the form that every problem that can be described in a given formalism can be evaluated efficiently on planar graphs, graph classes of small tree width, etc. In this way, one can easily verify that a problem is tractable on a certain class of graphs, but simply formalising the problem in a suitable logical formalism.
In this talk we will give an overview of known results in this area and present some of the methods used in their proofs. We will also present some new results. One is a generalisation of algorithmic results on graphs excluding a fixed minor to a larger class of graphs including bounded degree graphs. Another application of the logical approach is a way to compute the set of excluded minors for certain classes of graphs.
Colloquium - 16:00
Algorithmic matroid theory has recently attracted a substantial amount of interest of researchers. Analogues of classical algorithmic results for graphs of bounded tree-width has been established for matroids of bounded branch-width (which are representable over finite fields). In the talk, we will survey the results and methods applied in this area and compare them to the results on graphs. At the end of the talk, we will present a new matroid decomposition that allows to extend some of the previous algorithmic results on matroids representable over finite fields to the class of all matroids.