2025/03/11 by Surabhi Chakrabartty, Chakrabartty, Surabhi, Ranveer Singh +1 · 1 citation
Mathematics · #05C31 #15A15 #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #G.2.1 #G.2.2 #Limits and Structures in Graph Theory #Markov Chains and Monte Carlo Methods #Random Matrices and Applications
paper · pdf · doi:10.48550/arxiv.2503.08128
openalex publication_date 2025/03/11 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Computing the permanent of a (0,1)-matrix is a well-known #P-complete problem. In this paper, we present an expression for the permanent of a bipartite graph in terms of the determinant of the graph and its subgraphs, obtained by successively removing rows and columns corresponding to vertices involved in vertex-disjoint 4k-cycles. Our formula establishes a general relationship between the permanent and the determinant for any bipartite graph. Since computing the permanent of a biadjacency matrix is equivalent to counting the number of its perfect matchings, this approach also provides a more efficient method for counting perfect matchings in certain types of bipartite graphs.