License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.MFCS.2020.43
URN: urn:nbn:de:0030-drops-127099
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/12709/
Go to the corresponding LIPIcs Volume Portal

Gupta, Chetan ; Sharma, Vimal Raj ; Tewari, Raghunath

Efficient Isolation of Perfect Matching in O(log n) Genus Bipartite Graphs

pdf-format:
LIPIcs-MFCS-2020-43.pdf (0.5 MB)

Abstract

We 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 such a 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 for O(log n) genus bipartite graphs.

BibTeX - Entry

@InProceedings{gupta_et_al:LIPIcs:2020:12709,
  author =	{Chetan Gupta and Vimal Raj Sharma and Raghunath Tewari},
  title =	{{Efficient Isolation of Perfect Matching in O(log n) Genus Bipartite Graphs}},
  booktitle =	{45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)},
  pages =	{43:1--43:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-159-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{170},
  editor =	{Javier Esparza and Daniel Kr{\'a}ΔΎ},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2020/12709},
  URN =		{urn:nbn:de:0030-drops-127099},
  doi =		{10.4230/LIPIcs.MFCS.2020.43},
  annote =	{Keywords: Logspace computation, High genus, Matching isolation}
}

Keywords: Logspace computation, High genus, Matching isolation
Collection: 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)
Issue Date: 2020
Date of publication: 18.08.2020

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI