*Wissenschaftliches Programm* † *Liste der Vortragenden*

Sektion 15
Dienstag, 19.09.2000, 16.00–16.20 Uhr, WIL C 103

Matching as the Intersection of Matroids

Bianca Spille, Otto-von-Guericke-Universitšt Magdeburg

The matching problem together with the optimization problem over the intersection of two matroids are in some sense the hardest combinatorial optimization problems that are known to be solvable by polynomial time algorithms.

In this talk, we study some connections between the matching problem and the intersection of matroids. We characterize when the set of matchings in the graph Kn can be represented as the intersection of a given number m of matroids in terms of necessary and sufficient conditions. This description leads in a natural way to an IP-formulation of the introduced problem, which can be solved by standard IP-solvers, for at least not too large values of n and m. We also present a characterization of all graphs for which the set of matchings is the intersection of at most two matroids. Although the matching problem is polynomially solvable and the rank quotient of any matching independence system is always at least 1/2, the set of matchings can in general not be written as the intersection of at most three matroids. Upper bounds on the number of matroids required to represent the matchings on any graph with n nodes as the intersection of finitely many matroids are studied. In fact, O( V~ --
  n) matroids can be constructed explicitely to yield such a representation.

This is joint work with Robert T. Firla.