#

### Volume 2008

#### Article 4

Published by Dept. CS U. Chicago. Copyright 2008 CJTCS and the author.

####
Some perfect matchings and perfect
half-integral matchings in NC

Raghav Kulkarni

Department of Computer Science

University of Chicago

Chicago, USA
Meena Mahajan

The Institute of Mathematical Sciences

Chennai 600 113, India

and

Kasturi R. Varadarajan

Department of Computer Science

The University of Iowa

Iowa City, IA 52242-1419 USA

*September 5, 2008*
*(Submitted September 19, 2007)*
##### Abstract

We show that for any class of bipartite graphs which is closed under
edge deletion and where the number of perfect matchings can be
counted in NC, there is a deterministic NC algorithm for finding a
perfect matching. In particular, a perfect matching can be found in
NC for planar bipartite graphs and K_{3,3}-free bipartite graphs
via this approach. A crucial ingredient is part of an interior-point
algorithm due to Goldberg, Plotkin, Shmoys and Tardos.
An easy observation allows this approach to handle
regular bipartite graphs as well.
We show, by a careful analysis of the polynomial time algorithm due
to Galluccio and Loebl, that the number of perfect
matchings in a graph of small O(log n) genus can be counted in
NC. So perfect matchings in small genus bipartite graphs can also be
found via this approach.

We then present a different algorithm for finding a perfect matching
in a planar bipartite graph. This algorithm is substantially
different from the algorithm described above, and also from the
algorithm of Miller and Naor, which predates the approach of
Goldberg et al. and tackles the same problem. Our new algorithm extends
to small genus bipartite graphs, but not to K_{3,3}-free bipartite
graphs. We next show that a non-trivial extension of this algorithm
allows us to compute a vertex of the fractional perfect matching
polytope (such a vertex is either a perfect matching or a
half-integral matching) in NC, provided the graph is planar or small
genus but * not necessarily bipartite*, and has a perfect
matching to begin with. This extension rekindles the hope for an
NC-algorithm to find a perfect matching in a non-bipartite planar
graph.

- Preformatted versions of the article
- Source materials for custom formatting