8
$\begingroup$

I have a $n\times n$ matrix $A$. It's terms are $a_{ij}=-x^{w_{ij}}$ if $i\neq j$ and $a_{ii}=\sum_{j=0}^{n+1} x^{w_{ij}}$ on the diagonal. The matrix is symmetric as $w_{ij}=w_{ji}$. Numbers $w_{ij}$ are arbitrary. (The matrix is not singular as the sum on the diagonal runs up to $n+1$.)

How can I compute the $(1+\varepsilon)$-approximate number of terms in the determinant of $A$ with exponent smaller than some given exponent $W$, in time polynomial in $n$ and $\varepsilon^{-1}$ and independent of the largest value $w_{ij}$?

As a black box, I can use an algorithm that counts the number of paths on a DAG, shorter than some threshold $L$ with error $(1+\varepsilon)^{\pm 1}$. I planned to calculate some LU-decomposition of $A$. Then I could get the determinant as a product of a polynomial number of polynomials with polynomial number of terms: $det(A)=\prod_i^N f_i(x)$ where $N\in O(poly(n))$ and each $f_i(x)$ has polynomially many terms. Now I would construct a DAG that represents the determinant: a monomial $x^{w_{ij}}$ would be represented two vertices connected by an edge with weight $w_{ij}$. A summation of polynomials $f(x)$ and $g(x)$ would be represented by two vertices connected in parallel by the graph that represents $f(x)$ and the graph that represents $g(x)$. The product of polynomials $f(x)g(x)$ would be represented by the graphs corresponding to $f(x)$ and $g(x)$ in series. All is well so far, I would construct the graph and approximately count paths shorter than the threshold from one end to the other. But the problem is that some polynomials $f(x)$ will have negative terms. That means that I need to keep track of the parity of individual paths, effectively making 2 copies of the DAG and switching between them when parity changes. In the end I have to calculate the paths that end up with negative parity and subtract them from the paths that end up with positive parity. This can kill my approximation ratio since I do not know the relationship between the number of positive and negative parity paths.

Is there a different way how to represent the determinant as a product of polynomial number of polynomials, hopefully without negative terms and without division? I need to avoid any actual determinant calculation, since the expansion may generate a polynomial with number of terms exponential in $n$.

The original intent is probably obvious: I am trying to count spanning trees shorter than some value $W$. The determinant of the matrix $A$ is a generating polynomial for these. Evaluating the polynomial fully would not give a FPTAS, since we can have at most $n^{n-2}$ distinct weight spanning trees (consider a complete graph with edges of lengths $2^i$ for edge $i$.)

In this case, it seems that applying some division-less LU decomposition and then counting paths with parity will not work: if we calculate the determinant according to the Leibniz formula $\det(A)=\sum_{\sigma\in S_n}sgn(\sigma)\prod_{i=1}^n A_{i,\sigma_i}$, the expansion will contain cyclic subgraphs that will eventually cancel out. But there can be many cyclic subgraphs, shorter than the MST. So if we set counting threshold to the value of the MST, we might make a large error in the subtraction, unless the LU decomposition somehow magically takes care of this.

$\endgroup$
  • $\begingroup$ The problem described in the last paragraph seems a bit like a fancy version of #Knapsack; perhaps this would be a good place to start. $\endgroup$ – Colin McQuillan Apr 19 '13 at 14:14
  • $\begingroup$ Yes. The FPTAS for counting number of paths on a DAG shorter than some threshold works in the same way as the #Knapsack FPTAS. However, such method is not directly applicable to the counting of spanning trees, since there is no implicit order on the edges or vertices of the spanning tree, which would allow us to formulate the DP. In other words: our ability to take or leave the $i$-th knapsack item depends only on the remaining space in the knapsack, not on which items with id smaller than $i$ did we take. For spanning trees on the other hand, we need to remember many previously chosen edges. $\endgroup$ – Rasto S. Apr 19 '13 at 17:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.