Combinatorics Seminar
When: Sunday, March 11, 10am
Where: Schreiber 309
Speaker: Raphael Yuster, University of Haifa
Title: Maximum matching in graphs with an excluded minor
Abstract:
We present a new randomized algorithm for finding a maximum
matching in H-minor free graphs. For every fixed H, our
algorithm runs in {O}(n^{3\omega/(\omega+3)}) < O(n^{1.326})
time, where n is the number of vertices of the input graph
and \omega < 2.376 is the exponent of matrix multiplication.
This improves upon the previous O(n^{1.5}) time bound obtained
by applying the O(m{n}^{1/2})-time algorithm of Micali and
Vazirani on this important class of graphs.
For graphs with bounded genus, which are special cases of
H-minor free graphs, we present a randomized algorithm for
finding a maximum matching in {O}(n^{\omega/2}) < O(n^{1.19})
time. This extends a previous randomized algorithm of Mucha
and Sankowski, having the same running time, that finds a
maximum matching in planar graphs.
We also present a deterministic algorithm with a running time
of O(n^{1+\omega/2}) < O(n^{2.19}) for counting the number of
perfect matchings in graphs with bounded genus. This algorithm
combines the techniques used by the algorithms above with the
counting technique of Kasteleyn. Using this algorithm we can
also count, within the same running time, the number of T-joins
in planar graphs. As special cases, we get algorithms for
counting Eulerian subgraphs (T=\phi) and odd subgraphs (T=V) of
planar graphs.
The proof uses tools from structural graph theory, computational
algebra, and linear algebra.
Joint work with Uri Zwick.