A Flat Wall Theorem for Matching Minors in Bipartite Graphs

In 1913, Pólya asked for which (0,1)-matrices A it is possible to create a new matrix A′ by changing some of the signs such that the permanent of A equals the determinant of A′. A combinatorial solution to this problem was found by Little in 1975; he found these matrices to be exactly the biadjacency matrices of bipartite graphs excluding K3,3 as a matching minor. Utilising ideas from graph minors theory, this characterisation was later shown to yield a polynomial time algorithm to compute the permanent of matrices which satisfy Little’s condition. By a seminal result of Valiant, computing the permanent of (0,1)-matrices in general is #P-hard; however, it can be observed that the tractability of the permanent is closely related to the exclusion of matchings minors in bipartite graphs.