Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR10-079 | 28th April 2010 19:03

Space Complexity of Perfect Matching in Bounded Genus Bipartite Graphs


Authors: Samir Datta, Raghav Kulkarni, Raghunath Tewari, N. V. Vinodchandran
Publication: 30th April 2010 20:29
Downloads: 3359


We investigate the space complexity of certain perfect matching
problems over bipartite graphs embedded on surfaces of constant genus
(orientable or non-orientable). We show that the problems of deciding
whether such graphs have (1) a perfect matching or not and (2) a
unique perfect matching or not, are in the logspace complexity class
\SPL. Since \SPL\ is contained in the logspace counting classes
$\oplus\L$ (in fact in \modk\ for all $k\geq 2$), \CeqL, and \PL, our
upper bound places the above-mentioned matching problems in these
counting classes as well. We also show that the search version,
computing a perfect matching, for this class of graphs is in
$\FL^{\SPL}$. Our results extend the same upper bounds for these
problems over bipartite planar graphs known earlier.

As our main technical result, we design a logspace computable and
polynomially bounded weight function which isolates a minimum weight
perfect matching in bipartite graphs embedded on surfaces of constant
genus. We use results from algebraic topology for proving the
correctness of the weight function.

ISSN 1433-8092 | Imprint