06067703

j

06067703 Datta, Samir Kulkarni, Raghav Tewari, Raghunath Vinodchandran, N.V. Space complexity of perfect matching in bounded genus bipartite graphs. J. Comput. Syst. Sci. 78, No. 3, 765-779 (2012). 2012 Elsevier Science (Academic Press), San Diego, CA EN space complexity perfect matching topological graph theory

doi:10.1016/j.jcss.2011.11.002

Summary: 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 log-space complexity class Stoic Probabilistic Log-space (SPL). Since SPL is contained in the log-space counting classes $\oplus L$ (in fact in $\mathrm{Mod}_k L$ for all $k\geqslant 2$), $\mathrm{C}_{=}\mathrm{L}$, 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 can be performed by a log-space transducer with an SPL oracle. Our results extend the same upper bounds for these problems over bipartite planar graphs known earlier. As our main technical result, we design a log-space 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.