Campus Event Calendar

Event Entry

What and Who

Count perfect matchings in planar graphs

Mingji Xia
Max-Planck-Institut für Informatik - D1
AG1 Mittagsseminar (own work)
AG 1  
AG Audience

Date, Time and Location

Thursday, 26 September 2013
30 Minutes
E1 4


The number of perfect matchings in planar graphs can be computed in polynomial time. The gadgets in this #Pl-PM problem are called matchgate, whose functions satisfy some identities. The famous FKT algorithm for #Pl-PM and the known matchgate identities, are based on the algorithm and Grassmann-Plücker identities of Pfaffian, respectively.

We prove the matchgate identities in a simpler way, by showing the functions of matchgates are in a closed set generated by two growth operations, called juxtaposition and jumper by Matthew Cook. Because of these identities, instead of all exponentially many values, polynomial many values are enough to record a matchgate function. These facts give a #Pl-PM algorithm directly. Using the known matchgate that simulates crossing, this new algorithm can be adapted to both Pfaffian and Determinant.


Mengji Xia
--email hidden
passcode not visible
logged in users only

Mengji Xia, 09/25/2013 16:37
Mengji Xia, 09/25/2013 16:36 -- Created document.