Deterministically Isolating a Perfect Matching in Bipartite Planar Graphs

Samir Datta, Raghav Kulkarni & Sambuddha Roy
We present a deterministic way of assigning small (log bit) weights to the edges of a bipartite planar graph so that the minimum weight perfect matching becomes unique. The isolation lemma as described in (Mulmuley et al. 1987) achieves the same for general graphs using a randomized weighting scheme, whereas we can do it deterministically when restricted to bipartite planar graphs. As a consequence, we reduce both decision and construction versions of the matching problem...