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.STACS.2016.10
URN: urn:nbn:de:0030-drops-57116
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2016/5711/
Go to the corresponding LIPIcs Volume Portal

Arora, Rahul ; Gupta, Ashu ; Gurjar, Rohit ; Tewari, Raghunath

Derandomizing Isolation Lemma for K3,3-free and K5-free Bipartite Graphs

pdf-format:
11.pdf (0.7 MB)

Abstract

The perfect matching problem has a randomized NC algorithm, using the celebrated Isolation Lemma of Mulmuley, Vazirani and Vazirani. The Isolation Lemma states that giving a random weight assignment to the edges of a graph ensures that it has a unique minimum weight perfect matching, with a good probability. We derandomize this lemma for K3,3-free and K5-free bipartite graphs. That is, we give a deterministic log-space construction of such a weight assignment for these graphs. Such a construction was known previously for planar bipartite graphs. Our result implies that the perfect matching problem for K3,3-free and K5-free bipartite graphs is in SPL. It also gives an alternate proof for an already known result – reachability for K3,3-free and K5-free graphs is in UL.

BibTeX - Entry

@InProceedings{arora_et_al:LIPIcs:2016:5711,
  author =	{Rahul Arora and Ashu Gupta and Rohit Gurjar and Raghunath Tewari},
  title =	{{Derandomizing Isolation Lemma for K3,3-free and K5-free Bipartite Graphs}},
  booktitle =	{33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016)},
  pages =	{10:1--10:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-001-9},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{47},
  editor =	{Nicolas Ollinger and Heribert Vollmer},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2016/5711},
  URN =		{urn:nbn:de:0030-drops-57116},
  doi =		{10.4230/LIPIcs.STACS.2016.10},
  annote =	{Keywords: bipartite matching, derandomization, isolation lemma, SPL, minor-free graph}
}

Keywords: bipartite matching, derandomization, isolation lemma, SPL, minor-free graph
Collection: 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016)
Issue Date: 2016
Date of publication: 16.02.2016

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