Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR10-201 | 5th January 2011 11:16

Perfect Matching in Bipartite Planar Graphs is in UL

RSS-Feed




Revision #1
Authors: Samir Datta, Raghav Kulkarni, Raghunath Tewari
Accepted on: 5th January 2011 11:16
Downloads: 5433
Keywords: 


Abstract:

We prove that Perfect Matching in bipartite planar graphs is in UL, improving upon
the previous bound of SPL (see [DKR10]) on its space complexity. We also exhibit space
complexity bounds for some related problems. Summarizing, we show that, constructing:
1. a Perfect Matching in bipartite planar graphs is in UL;
2. a Hall Obstacle in bipartite planar graphs is in NL;
3. an Even Perfect Matching in bipartite planar graphs is in NL; and
4. an Even Path in planar DAGs is in UL.
For the proof of 2 and 3, we revisit the flow technique of Miller and Naor [MN89]
which was used to provide an NC algorithm for bipartite planar matching construction.
To obtain the main result (item 1 above), we combine it in a simple but subtle way with
the double counting technique of Reinhardt and Allender [RA00] to yield the UL bound.
To prove the UL bound in 4 above, we combine two existing isolation techniques (viz.
[BTV09] and [FKS84, Hoa10]) in a non-obvious way.


Paper:

TR10-201 | 21st December 2010 18:21

Perfect Matching in Bipartite Planar Graphs is in UL





TR10-201
Authors: Samir Datta, Raghav Kulkarni, Raghunath Tewari
Publication: 26th December 2010 17:56
Downloads: 4779
Keywords: 


Abstract:

We prove that Perfect Matching in bipartite planar graphs is in UL, improving upon
the previous bound of SPL (see [DKR10]) on its space complexity. We also exhibit space
complexity bounds for some related problems. Summarizing, we show that, constructing:
1. a Perfect Matching in bipartite planar graphs is in UL;
2. a Hall Obstacle in bipartite planar graphs is in NL;
3. an Even Perfect Matching in bipartite planar graphs is in NL; and
4. an Even Path in planar DAGs is in UL.
For the proof of 2 and 3, we revisit the flow technique of Miller and Naor [MN89]
which was used to provide an NC algorithm for bipartite planar matching construction.
To obtain the main result (item 1 above), we combine it in a simple but subtle way with
the double counting technique of Reinhardt and Allender [RA00] to yield the UL bound.
To prove the UL bound in 4 above, we combine two existing isolation techniques (viz.
[BTV09] and [FKS84, Hoa10]) in a non-obvious way.



ISSN 1433-8092 | Imprint