AG 1, AG 2, AG 3, INET, AG 4, AG 5, D6, SWS, RG1, MMCI   Info

AG Audience

English

30 Minutes

Parallel algorithms for graph matching problems have been extensively studied since the 1970s. Graph matching problems behave very differently in parallel compared to their sequential counterparts, which makes them extremely fascinating to study. For example, in sequential models of computation, counting the number of perfect matchings in a graph is generally considered to be a harder problem than searching for a perfect matching, with the latter being in P and the former being #P-complete (for bipartite graphs). However, an NC algorithm for counting planar perfect matchings has been known since the 1980s, while the first NC algorithm for searching for a planar perfect matching was only discovered as recently as in 2017 by Anari and Vazirani. 

I will discuss a particularly elegant approach to parallel matching which was proposed by Mulmuley, Vazirani, and Vazirani in their 1987 paper ‘Matching is as Easy as Matrix Inversion’. Their paper introduced the celebrated isolation lemma and used it to prove that searching for perfect matchings in bipartite graphs can be done in RNC.

I will also discuss approaches to de-randomise this algorithm, particularly those proposed by Datta, Kulkarni, and Roy in "Deterministically Isolating a Perfect Matching in Bipartite Planar Graphs" and by Tewari and Vinodchandran in “Green’s Theorem and Isolation in Planar Graphs”.

Jennifer Gerling

+49 681 9325 1801

--email hidden

Zoom

passcode not visible

logged in users only