ECCC-Report TR14-161https://eccc.weizmann.ac.il/report/2014/161Comments and Revisions published for TR14-161en-usTue, 29 Dec 2015 07:01:45 +0200
Revision 2
| Derandomizing Isolation Lemma for $K_{3,3}$-free and $K_5$-free Bipartite Graphs |
Rohit Gurjar,
Rahul Arora,
Ashu Gupta,
Raghunath Tewari
https://eccc.weizmann.ac.il/report/2014/161#revision2The 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$.Tue, 29 Dec 2015 07:01:45 +0200https://eccc.weizmann.ac.il/report/2014/161#revision2
Revision 1
| Derandomizing Isolation Lemma for $K_{3,3}$-free and $K_5$-free Bipartite Graphs |
Rohit Gurjar,
Rahul Arora,
Ashu Gupta,
Raghunath Tewari
https://eccc.weizmann.ac.il/report/2014/161#revision1The 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$.Mon, 28 Dec 2015 11:45:10 +0200https://eccc.weizmann.ac.il/report/2014/161#revision1
Paper TR14-161
| Derandomizing Isolation Lemma for $K_{3,3}$-free and $K_5$-free Bipartite Graphs |
Rohit Gurjar,
Rahul Arora,
Ashu Gupta,
Raghunath Tewari
https://eccc.weizmann.ac.il/report/2014/161The 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$.Thu, 27 Nov 2014 20:33:34 +0200https://eccc.weizmann.ac.il/report/2014/161