CJTCS Volume 2008 Article 4

Volume 2008

Article 4

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
- DVI (113,896 bytes)
- PostScript (462,659 bytes)
- PDF (281,443 bytes)
Source materials for custom formatting
- LaTeX (cj08-04.tex, (79,405 bytes) needs .eps files for figures, in this directory.
- Bibliography (cj08-04.bbl, 7,770 bytes)
- Parameter settings for custom formatting (cjropts.tex, 165 bytes)
- Self citation in BIBTeX (259 bytes)

DOI: 10.4086/cjtcs.2008.004

Volume 2008, Article 3
[back]

Volume 2008 [back]

Published articles