2026-07-22T12:29:06Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:1346 2024-03-06T10:32:58Z ddc:004 open_access

Deterministically Isolating a Perfect Matching in Bipartite Planar Graphs Datta, Samir Kulkarni, Raghav Roy, Sambuddha 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 to testing whether a matrix is singular, under the promise that its determinant is $0$ or $1$, thus obtaining a highly parallel SPL algorithm for bipartite planar graphs. This improves the earlier known bounds of non-uniform SPL by (Allender et al. 1999) and $NC^2$ by (Miller and Naor 1995, Mahajan and Varadarajan 2000). It also rekindles the hope of obtaining a deterministic parallel algorithm for constructing a perfect matching in non-bipartite planar graphs, which has been open for a long time. Our techniques are elementary and simple. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Samir Datta and Raghav Kulkarni and Sambuddha Roy 2008 Is Part Of LIPIcs, Volume 1, 25th International Symposium on Theoretical Aspects of Computer Science (2008) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2008.1346 urn:nbn:de:0030-drops-13465 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2008.1346 eng https://creativecommons.org/licenses/by-nd/3.0/legalcode