Perfect Matching in Bipartite Planar Graphs is in UL.
Samir K. Datta, Raghav Kulkarni, Raghunath Tewari · Electronic colloquium on computational complexity · 2010
We prove that Perfect Matching in bipartite planar graphs is in UL, improving upon the previous bound of SPL (see [DKR10]) on its space complexity. We also exhibit space complexity bounds for some related problems. Summarizing, we show that, constructing: 1. a Perfect Matching in bipartite planar graphs is in UL 2. a Hall Obstacle in bipartite planar graphs is in NL; 3. an Even Perfect Matching in bipartite planar graphs is in NL; and 4. an Even Path in planar DAGs is in UL. For the proof of 2 and 3, we revisit the flow technique of Miller and Naor [MN89] which was used to provide an NC algorithm for bipartite planar matching construction. To obtain the main result (item 1 above), we combine it in a simple but subtle way with the double counting technique of Reinhardt and Allender [RA00] to yield the UL bound. To prove the UL bound in 4 above, we combine two existing isolation techniques (viz. [BTV09] and [FKS84, Hoa10]) in a non-obvious way.