Revision #2 Authors: Rahul Arora, Ashu Gupta, Rohit Gurjar, Raghunath Tewari

Accepted on: 29th December 2015 07:01

Downloads: 1398

Keywords:

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 formatting and presentation.

Revision #1 Authors: Rahul Arora, Ashu Gupta, Rohit Gurjar, Raghunath Tewari

Accepted on: 28th December 2015 11:45

Downloads: 980

Keywords:

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 mostly in the presentation.

TR14-161 Authors: Rahul Arora, Ashu Gupta, Rohit Gurjar, Raghunath Tewari

Publication: 27th November 2014 20:33

Downloads: 1626

Keywords:

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$.