ECCC-Report TR20-025https://eccc.weizmann.ac.il/report/2020/025Comments and Revisions published for TR20-025en-usMon, 24 Feb 2020 12:15:00 +0200
Paper TR20-025
| Efficient Isolation of Perfect Matching in O(log n) Genus Bipartite Graphs |
Chetan Gupta,
Vimal Raj Sharma,
Raghunath Tewari
https://eccc.weizmann.ac.il/report/2020/025We show that given an embedding of an O(log n) genus bipartite graph, one can construct an edge weight function in logarithmic space, with respect to which the minimum weight perfect matching in the graph is unique, if one exists.
As a consequence, we obtain that deciding whether the graph has a perfect matching or not is in SPL. In 1999, Reinhardt, Allender and Zhou proved that if one can construct a polynomially bounded weight function for a graph in logspace such that it isolates a minimum weight perfect matching in the graph, then the perfect matching problem can be solved in SPL. In this paper, we give a deterministic logspace construction of such a weight function.Mon, 24 Feb 2020 12:15:00 +0200https://eccc.weizmann.ac.il/report/2020/025