Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
430727 | Journal of Computer and System Sciences | 2012 | 15 Pages |
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 ⊕L⊕L (in fact in ModkL for all k⩾2k⩾2), C=LC=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.
► We show that deciding whether a bipartite bounded genus graph has a perfect matching is in SPL. ► We also show that computing a perfect matching, for this class of graphs is in FLSPLFLSPL. ► We design a log-space computable and weight function to isolate the minimum weight perfect matching in such graphs. ► We also give a combinatorial embedding of such graphs in an appropriate fundamental polygon in log-space.