Permanent of bipartite graphs in terms of determinants
Surabhi Chakrabartty, Ranveer Singh · 2025
Read Permanent of bipartite graphs in terms of determinants by Surabhi Chakrabartty, Ranveer Singh (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2503-08128.txt.
Introduction
Surabhi Chakrabartty and Ranveer Singh give a 2025 formula that ties a hard counting number for two sided graphs to an easier signed count. The hard number, the permanent of a zero one grid, counts perfect pairings but is famed as costly to compute. The easier number is the determinant of the same grid.
Their formula builds the permanent from the determinant of the graph and of smaller graphs cut from it. Cuts remove rows and columns tied to sets of disjoint short cycles. For some graph types, the route counts pairings faster than brute force. The result links two classic grid measures in a general way.
Catalog record
| CREATOR | Surabhi Chakrabartty, Ranveer Singh |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 27 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2503-08128
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Permanent of bipartite graphs in terms of determinants Surabhi Chakrabartty, Ranveer Singh Abstract Computing the permanent of a ( 0 , 1 ) (0,1) -matrix is a well-known # P \#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 4 k 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. 1 Introduction A graph G=(V,E) consists of a vertex set V=\{v_{1},\ldots,v_{n}\} and an edge set E . It is said to be simple if it does not contain loops or multiple edges between a pair of vertices, and it is said to be undirected if the edges have no direction associated with them. In this paper, we will be concerned with simple and undirected graphs only. Adjacency matrix A(G) of a graph G with n vertices is an n\times n matrix defined by A(G)=(a_{ij}) where \displaystyle a_{ij}=\begin{cases}1,&\text{if there is an edge between }v_{i}\text{ and }v_{j},\\ 0,&\text{otherwise}.\end{cases} A matching in a graph is a subset of edges such that no two edges share a common vertex. A perfect matching is a matching that covers every vertex of the graph. It is evident that a graph with an odd number of vertices cannot have a perfect matching. While determining the existence of a perfect matching in a general graph can be done efficiently [ 4 ] , counting the number of perfect matchings is computationally very hard. A graph is said to be bipartite if its vertex set can be divided into two disjoint sets, such that no two vertices within the same set are adjacent. Given a bipartite graph G=(U,V,E) , its biadjacency matrix is a |U|\times|V| matrix defined by B(G)=(b_{ij}) where \displaystyle b_{ij}=\begin{cases}1,&\text{if there is an edge between }u_{i}\in U\text{ and }v_{j}\in V,\\ 0,&\text{otherwise}.\end{cases} The determinant and permanent of an n\times n matrix M=(a_{ij}) are defined as \det(M)=\sum_{\sigma\in S_{n}}\sign(\sigma)\prod_{i=1}^{n}a_{i,\sigma(i)},\;\; and \per(M)=\sum_{\sigma\in S_{n}}\prod_{i=1}^{n}a_{i,\sigma(i)}, respectively, where S_{n} is the set of all permutations of \{1,2,\dots,n\} , the sign function \sign(\sigma) is 1, if \sigma is even and -1 if \sigma is odd, respectively. While the determinant of any matrix can be computed in \mathcal{O}(n^{2.37}) , computing the permanent is known to be \#P -complete even for a (0,1) -matrix [ 14 ] . The determinant and permanent of a graph are defined as the determinant and permanent associated with its adjacency matrix, respectively. We denote them by \det(G) and \per(G) . The Pólya Permanent Problem [ 9 ] asks under what conditions the signs of certain nonzero entries in a (0,1) -matrix A can be adjusted to obtain a matrix B such that \per(A)=\det(B) . This problem is known to be equivalent to twenty-three other graph-theoretic problems [ 7 , 10 ] , including the problem of counting the number of perfect matchings in bipartite graphs. For a detailed survey and a complete characterization of minor-closed graph classes where perfect matchings can be computed efficiently, see [ 13 ] . While computing the permanent of a general matrix M is intractable in general, when M is the biadjacency matrix of a bipartite planar graph, the permanent can be computed in polynomial time by reducing it to the Pfaffian of a suitably constructed skew-symmetric matrix, as established by Kasteleyn [ 6 ] . Beyond its role in graph theory, the permanent also has important applications in quantum computing [ 1 ] . In Boson sampling, it helps determine the probability amplitudes of photon distributions in linear optical networks. It also shows up in statistical physics, particularly in models like the dimer model and monomer-dimer model, which are used to study phase transitions and other physical phenomena. Writing the permanent as a function of the determinant has been a longstanding problem, more generally referred to as the Permanent vs. Determinant problem. In this paper, we aim to establish a relationship between the permanent and determinant of bipartite graphs using graph-theoretic concepts. As a corollary of this relation, we also observe the fact that the absence of 4k -cycles in a bipartite graph guarantees that the permanent and determinant have the same absolute value. This formulation will not only provide insights into their general relationship but will also facilitate more efficient computation of the permanent for certain types of bipartite graphs. A cycle of length l is a sequence of distinct vertices u_{1},u_{2},\dots,u_{l} such that u_{i}\sim u_{i+1} for i=1,\dots,l-1 and u_{l}\sim u_{1} . A 4k -cycle is a cycle with a length that is a multiple of four. Likewise, a (4k+2) -cycle is a cycle whose length exceeds a multiple of four by two. Since bipartite graphs do not contain odd-length cycles, the only cycles they can contain are 4k -cycles and (4k+2) -cycles. We denote the set of all 4k -cycles and (4k+2) -cycles of a graph G by C_{4k}(G) and C_{4k+2}(G) , respectively. We use the notation T_{z} to represent any ordered tuple of z mutually vertex-disjoint 4k -cycles. Note that T_{1} simply denotes any 4k -cycle in the graph, as a single cycle is always vertex-disjoint by definition. 1 2 3 4 5 6 7 8 9 10 Figure 1: Example of a bipartite graph Example 1 Consider the graph G shown in Figure 1 . The cycles in G are: C_{1}=(1,2,3,4,1),C_{2}=(3,4,5,6,3),C_{3}=(7,8,9,10,7),C_{4}=(1,2,3,6,5,4,1), Then the set of 4k -cycles in G is given by C_{4k}(G)=\{C_{1},C_{2},C_{3}\}, and the set of (4k+2) -cycles is C_{4k+2}(G)=\{C_{4}\}. Now, the single-cycle tuples are: \displaystyle T_{1}^{1}=C_{1},\quad T_{1}^{2}=C_{2},\quad T_{1}^{3}=C_{3}. The two-cycle vertex-disjoint tuples are: \displaystyle T_{2}^{1}=(C_{1},C_{3}),\quad T_{2}^{2}=(C_{2},C_{3}),\quad T_{2}^{3}=(C_{3},C_{1}),\quad T_{2}^{4}=(C_{3},C_{2}). The rest of the paper is organized as follows: In Section 2 , we give the graph-theoretic interpretation of the permanent by introducing Sachs subgraphs. In the main result (Section 3 ), we demonstrate how the determinant of the submatrices obtained after removing rows and columns corresponding to 4k -cycles can be used to compute the permanent of a bipartite graph. Finally, in the discussion (Section 4 ), we provide a few conditions such that the permanent of such a type of bipartite graph can be computed efficiently. 2 Permanent using Sachs Subgraphs A Sachs subgraph is a subgraph in which every component is either a cycle or an individual edge. We observe that, for a bipartite graph, there is no Sachs subgraph on an odd number of vertices, as bipartite graphs do not contain odd-length cycles. We will use the notation U_{i} to denote any Sachs subgraph of G on i vertices. In the graph shown in Figure 1 , some possible Sachs subgraphs on six vertices are \displaystyle U_{6}^{1} \displaystyle=\{C_{4}\},\quad U_{6}^{2}=\{C_{1}\cup(5,6)\},\quad U_{6}^{3}=\{C_{1}\cup(7,8)\}, \displaystyle U_{6}^{4} \displaystyle=\{C_{2}\cup(1,2)\},\quad U_{6}^{5}=\{C_{3}\cup(3,4)\}, \displaystyle U_{6}^{6} \displaystyle=\{(1,4)\cup(6,9)\cup(7,8)\},\quad U_{6}^{7}=\{(1,2)\cup(3,4)\cup(5,6)\}. In total, there are 94 Sachs subgraphs of G on six vertices. Some possible Sachs subgraphs of G on four vertices are \displaystyle U_{4}^{1} \displaystyle=\{C_{1}\},\quad U_{4}^{2}=\{C_{2}\},\quad U_{4}^{3}=\{C_{3}\}. \displaystyle U_{4}^{4} \displaystyle=\{(2,3)\cup(9,10)\},\quad U_{4}^{5}=\{(3,6)\cup(1,2)\}. In total, there are 51 Sachs subgraphs of G