Excluding a single-crossing matching minor

By a seminal result of Valiant, computing the permanent of (0,1)-matrices is #P-hard. In 1913 Polya asked for which (0,1)-matrices A it is possible to change some signs such that the permanent of A equals the determinant of the resulting matrix. This, eventually, lead to a polynomial time algorithm to compute the permanent of (0,1)-matrices whose associated bipartite graph excludes K_3,3 as a matching minor. Recently it was shown that the exclusion of any planar bipartite graph as a matching minor yields a class of bipartite graphs on which the permanent of the corresponding (0,1)-matrices can be computed efficiently.

We identify a class of bipartite graphs strictly generalising planar bipartite graphs and K_3,3 which includes infinitely many non-Pfaffian graphs. The exclusion of any member of this class as a matching minor yields a structure that allows for the efficient evaluation of the permanent. Moreover, we show that the evaluation of the permanent remains #P-hard on bipartite graphs which exclude K_5,5 as a matching minor.

This is joint work with Archontia C. Giannopoulou and Dimitrios M. Thilikos.

Join Zoom Meeting Here!

Everyone is welcome and encouraged to attend.