2022/12/19 by Archontia C. Giannopoulou, Giannopoulou, Archontia C., Dimitrios M. Thilikos +3 · 1 citation
Computer Science · Mathematics · #05C83 #05C85 #68R05 #68R10 #Advanced Graph Theory Research #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #F.2.2 #FOS: Computer and information sciences #FOS: Mathematics #G.2.2 #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.2212.09348
openalex publication_date 2022/12/19 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
\noindent 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 biadjacency matrices of bipartite graphs excluding K3,3 as a \matching minor. This was turned into a polynomial time algorithm by McCuaig, Robertson, Seymour, and Thomas in 1999. However, the relation between the exclusion of some matching minor in a bipartite graph and the tractability of the permanent extends beyond K3,3. 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. In this paper we unify the two results above into a single, more general result in the style of the celebrated structure theorem for single-crossing-minor-free graphs. We identify a class of bipartite graphs strictly generalising planar bipartite graphs and K3,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 K5,5 as a matching minor. This establishes a first computational lower bound for the problem of counting perfect matchings on matching minor closed classes.