What are some methods for representing a weighted directed graph with a non-weighted directed graph while preserving some properties?

Question

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.

Answer 1

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.