2 Search Results for "Arora, Rahul"


Document
Planar Maximum Matching: Towards a Parallel Algorithm

Authors: Samir Datta, Raghav Kulkarni, Ashish Kumar, and Anish Mukherjee

Published in: LIPIcs, Volume 123, 29th International Symposium on Algorithms and Computation (ISAAC 2018)


Abstract
Perfect matchings in planar graphs have been extensively studied and understood in the context of parallel complexity [P W Kastelyn, 1967; Vijay Vazirani, 1988; Meena Mahajan and Kasturi R. Varadarajan, 2000; Datta et al., 2010; Nima Anari and Vijay V. Vazirani, 2017]. However, corresponding results for maximum matchings have been elusive. We partly bridge this gap by proving: 1) An SPL upper bound for planar bipartite maximum matching search. 2) Planar maximum matching search reduces to planar maximum matching decision. 3) Planar maximum matching count reduces to planar bipartite maximum matching count and planar maximum matching decision. The first bound improves on the known [Thanh Minh Hoang, 2010] bound of L^{C_=L} and is adaptable to any special bipartite graph class with non-zero circulation such as bounded genus graphs, K_{3,3}-free graphs and K_5-free graphs. Our bounds and reductions non-trivially combine techniques like the Gallai-Edmonds decomposition [L. Lovász and M.D. Plummer, 1986], deterministic isolation [Datta et al., 2010; Samir Datta et al., 2012; Rahul Arora et al., 2016], and the recent breakthroughs in the parallel search for planar perfect matchings [Nima Anari and Vijay V. Vazirani, 2017; Piotr Sankowski, 2018].

Cite as

Samir Datta, Raghav Kulkarni, Ashish Kumar, and Anish Mukherjee. Planar Maximum Matching: Towards a Parallel Algorithm. In 29th International Symposium on Algorithms and Computation (ISAAC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 123, pp. 21:1-21:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)


Copy BibTex To Clipboard

@InProceedings{datta_et_al:LIPIcs.ISAAC.2018.21,
  author =	{Datta, Samir and Kulkarni, Raghav and Kumar, Ashish and Mukherjee, Anish},
  title =	{{Planar Maximum Matching: Towards a Parallel Algorithm}},
  booktitle =	{29th International Symposium on Algorithms and Computation (ISAAC 2018)},
  pages =	{21:1--21:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-094-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{123},
  editor =	{Hsu, Wen-Lian and Lee, Der-Tsai and Liao, Chung-Shou},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2018.21},
  URN =		{urn:nbn:de:0030-drops-99695},
  doi =		{10.4230/LIPIcs.ISAAC.2018.21},
  annote =	{Keywords: maximum matching, planar graphs, parallel complexity, reductions}
}
Document
Derandomizing Isolation Lemma for K3,3-free and K5-free Bipartite Graphs

Authors: Rahul Arora, Ashu Gupta, Rohit Gurjar, and Raghunath Tewari

Published in: LIPIcs, Volume 47, 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016)


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.

Cite as

Rahul Arora, Ashu Gupta, Rohit Gurjar, and Raghunath Tewari. Derandomizing Isolation Lemma for K3,3-free and K5-free Bipartite Graphs. In 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 47, pp. 10:1-10:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)


Copy BibTex To Clipboard

@InProceedings{arora_et_al:LIPIcs.STACS.2016.10,
  author =	{Arora, Rahul and Gupta, Ashu and Gurjar, Rohit and Tewari, Raghunath},
  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 =	{Ollinger, Nicolas and Vollmer, Heribert},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2016.10},
  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}
}
  • Refine by Author
  • 1 Arora, Rahul
  • 1 Datta, Samir
  • 1 Gupta, Ashu
  • 1 Gurjar, Rohit
  • 1 Kulkarni, Raghav
  • Show More...

  • Refine by Classification
  • 1 Theory of computation → Parallel algorithms

  • Refine by Keyword
  • 1 SPL
  • 1 bipartite matching
  • 1 derandomization
  • 1 isolation lemma
  • 1 maximum matching
  • Show More...

  • Refine by Type
  • 2 document

  • Refine by Publication Year
  • 1 2016
  • 1 2018

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail