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 #2 to TR14-161 | 29th December 2015 07:01

Derandomizing Isolation Lemma for $K_{3,3}$-free and $K_5$-free Bipartite Graphs

RSS-Feed




Revision #2
Authors: Rahul Arora, Ashu Gupta, Rohit Gurjar, Raghunath Tewari
Accepted on: 29th December 2015 07:01
Downloads: 1297
Keywords: 


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 $K_{3,3}$-free and $K_5$-free bipartite graphs, i.e. 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 $K_{3,3}$-free and $K_5$-free bipartite graphs is in $SPL$.

It also gives an alternate proof for an already known result -- reachability for $K_{3,3}$-free and $K_5$-free graphs is in $UL$.



Changes to previous version:

Changes to formatting and presentation.


Revision #1 to TR14-161 | 28th December 2015 11:45

Derandomizing Isolation Lemma for $K_{3,3}$-free and $K_5$-free Bipartite Graphs





Revision #1
Authors: Rahul Arora, Ashu Gupta, Rohit Gurjar, Raghunath Tewari
Accepted on: 28th December 2015 11:45
Downloads: 876
Keywords: 


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 $K_{3,3}$-free and $K_5$-free bipartite graphs, i.e. 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 $K_{3,3}$-free and $K_5$-free bipartite graphs is in $SPL$.

It also gives an alternate proof for an already known result -- reachability for $K_{3,3}$-free and $K_5$-free graphs is in $UL$.



Changes to previous version:

Changes mostly in the presentation.


Paper:

TR14-161 | 27th November 2014 15:18

Derandomizing Isolation Lemma for $K_{3,3}$-free and $K_5$-free Bipartite Graphs





TR14-161
Authors: Rahul Arora, Ashu Gupta, Rohit Gurjar, Raghunath Tewari
Publication: 27th November 2014 20:33
Downloads: 1507
Keywords: 


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 $K_{3,3}$-free and $K_5$-free bipartite graphs, i.e. 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 $K_{3,3}$-free and $K_5$-free bipartite graphs is in $SPL$.

It also gives an alternate proof for an already known result -- reachability for $K_{3,3}$-free and $K_5$-free graphs is in $UL$.



ISSN 1433-8092 | Imprint