Monday, July 7, 2008
Technische Universität Berlin
Fakultät II, Institut für Mathematik
Str. des 17. Juni 136,
room MA 041
Lecture - 14:15
A graph is called perfect if for every induced subgraph, the size of its largest clique equals the minimum number of colors needed to color its vertices. As it turns out, the notion of perfect graphs generalizes a large number of phenomena, both in graph theory and in combinatorial optimization. Therefore, the problems of charactering perfect (or minimal imperfect) graphs and finding an efficient recognition algorithm have become well known in both communities. In 1960's Claude Berge made a conjecture that any graph with no induced odd cycles of length greater than three or their complements is perfect (thus, odd cycles of length greater than three and their complements are the only minimal imperfect graphs). This conjecture is known as the Strong Perfect Graph Conjecture.
We call graphs containing no induced odd cycles of length greater than three or their complements Berge graphs. A stronger conjecture was made by Conforti, Cornuejols and Vuskovic, that any Berge graph either belongs to one of a few well understood basic classes or has a decomposition that can not occur in a minimal counterexample to Berge's Conjecture. In joint work with Neil Robertson, Paul Seymour and Robin Thomas we were able to prove this conjecture and consequently the Strong Perfect Graph Theorem.
Later, in joint work with G. Cornuejols, X, Lui, P.Seymour and K. Vuskovic, we found an algorithm that tests in polynomial time whether a graph is Berge, and therefore perfect.
In my talk I will give an overview of both these results.
Colloquium - 16:00
A discrete optimization problem is often modeled as the problem to find an integral vector x which optimizes a linear function over a set of inequalities specified by a 0-1 matrix A and an integral vector r. Note that problems of this type cannnot be solved efficiently in general. However, since each row of the 0-1 matrix A can be identified with a subset of the column set, we may take the structure of the corresponding row set family into account. We present a greedy-type algorithm for solving the problem if the set family is endowed with a certain partial order: the poset forms a consecutive lattice on which r is submodular. Our model fits into the framework of Hoffman and Schwartz' lattice polyhedra and covers optimization problems such as finding shortest paths or arborescences in a digraph, an optimal basis of a polymatroid, or a maximum flow in a planar graph. This is joint work with Ulrich Faigle.