Name
Abstract | ||
|---|---|---|
The independence polynomial has been widely studied algebraic graph theory, statistical physics, and algorithms for counting and sampling problems. Seminal results of Weitz (2006) and Sly (2010) have shown the that the computational complexity of approximating the independence polynomial with positive activities is tightly linked to a uniqueness phase transition for a Gibbs measure. We study algorithms for approximating the independence polynomial with negative and complex arguments. The independence polynomial with complex arguments may not have a counting interpretation, but it does have strong connections to combinatorics and to statistical physics. The independence polynomial with negative arguments determines the maximal region of probabilities to which the Lovu0027{a}sz Local Lemma (LLL) can be extended, and also gives a lower bound on the probability the LLLu0027s conclusion (Shearer 1985). In statistical physics, complex (and negative) zeros of the independence polynomial relate to existence of phase transitions (Penrose 1963). Whereas many algorithms for computing combinatorial polynomials are restricted to the univariate setting, we consider the multivariate independence polynomial, since there is a natural multivariate region of interest -- Sheareru0027s region for the LLL. Our main result is: for any $n$-vertex graph of degree at most $d$, any $alpha in (0,1]$, and any complex vector $p$ such that $(1+alpha) cdot p$ lies Sheareru0027s region, there is a deterministic algorithm to approximate the independence polynomial at $p$ within $(1+epsilon)$ multiplicative error and with runtime $(frac{n}{epsilon alpha})^{O(log(d)/alpha)}$. Our results also extend to graphs of unbounded degree that have a bounded connective constant. We also give hardness results addressing the dependence of the runtime of the algorithm on the above parameters. |
Year | Venue | Field |
|---|---|---|
2016 | arXiv: Data Structures and Algorithms | Gibbs measure,Uniqueness,Discrete mathematics,Combinatorics,Multiplicative function,Polynomial,Upper and lower bounds,Degree of a polynomial,Algebraic graph theory,Mathematics,Bounded function |
DocType | Volume | Citations |
Journal | abs/1608.02282 | 6 |
PageRank | References | Authors |
0.59 | 25 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Nicholas J. A. Harvey | 1 | 909 | 57.85 |
| Piyush Srivastava | 2 | 19 | 2.99 |
| Jan Vondrák | 3 | 59 | 5.10 |