Space Complexity of Perfect Matching in Bounded Genus Bipartite Graphs

Samir Datta, Raghav Kulkarni, Raghunath Tewari & N. Variyam Vinodchandran
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 mod_k for all k >= 2), C=L,...