-
Sebastian Wiederrecht, Excluding single-crossing matching minors in bipartite graphs
Sebastian Wiederrecht, Excluding single-crossing matching minors in bipartite graphs
By a seminal result of Valiant, computing the permanent of (0, 1)-matrices is, in general, #P-hard. In 1913 Pólya 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. In 1975, Little showed these matrices to be exactly the …