Computing the Permanental Polynomial of Bipartite Graphs

The computation of the permanental polynomial of a matrix is a well-known computationally hard problem, even for (0, 1)-matrices. We define a modified characteristic polynomial by altering the signs of certain coefficients in the characteristic polynomial, and show that the permanental polynomial can be expressed as a linear combination of modified characteristic polynomials of subgraphs obtained by successively removing vertex-disjoint 4 k -cycles.