4
$\begingroup$

More specifically, I'm looking at the problem of applying an algorithm for computing the permanent of a sparse matrix of binary entries (0s and 1s) to a matrix that has entries of positive and negative integers (but still sparsely).

I am not sure how hard this is. Clearly the permanent of a general matrix can be negative so it cannot be written as the permanent of a matrix with non-negative entries.

However, there may be some kind of way to re-represent the permanent of the general matrix in terms of other permanents.

That is, Per(A) = Per(A1) +/- Per(A2) +/- Per(A3) +/-... for some matrices A1,A2,A3, or something like that.

This is related to the problem of rerepresenting weighted graphs as non-weighted graphs through the connection of the permanent and cycle covers on the adjacency graph.

$\endgroup$

1 Answer 1

7
$\begingroup$

The problem of computing the permanent of general matrices can indeed be reduced to the problem of computing the permanent of 0-1 matrices. This was shown in the paper that introduced the complexity class #P in 1979 [1] (which also showed that the problem is #P-complete).

There's a nice article that covers this on Wikipedia, based on a simpler proof published later [2].

As you mentioned sparse matrices particularly you may wish to know that if the matrix is the biadjacency matrix of a planar graph then the permanent can be computed in polynomial-time using the FKT algorithm. This is a consequence of the permanent of the biadjacency matrix of a bipartite graph being equal to the weighted sum of perfect matchings, as explained here. There's a previous question related to this.

[1] L. G. Valiant. The complexity of computing the permanent. Theor. Comput. Sci., 8:189-201, 1979. Available here.
[2] A. Ben-Dor and S. Halevi. Zero-one permanent is #P-complete, a simpler proof. Proceedings of the 2nd Israel Symposium on the Theory and Computing Systems, pages 108–117, 1993. Available from the author's webpage here.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.