Computer Science – Computational Complexity

Scientific paper

[
0.00
] – not rated yet
Voters
0
Comments 0

2011-05-25

Computer Science

Computational Complexity

Scientific paper

We study the computational complexity of approximately counting the number of independent sets of a graph with maximum degree Delta. More generally, for an input graph G=(V,E) and an activity lambda>0, we are interested in the quantity Z_G(lambda) defined as the sum over independent sets I weighted as w(I) = lambda^|I|. In statistical physics, Z_G(lambda) is the partition function for the hard-core model, which is an idealized model of a gas where the particles have non-negibile size. Recently, an interesting phase transition was shown to occur for the complexity of approximating the partition function. Weitz showed an FPAS for the partition function for any graph of maximum degree Delta when Delta is constant and lambda< lambda_c(Tree_Delta):=(Delta-1)^(Delta-1)/(Delta-2)^Delta. The quantity lambda_c(Tree_Delta) is the critical point for the so-called uniqueness threshold on the infinite, regular tree of degree Delta. On the other side, Sly proved that there does not exist efficient (randomized) approximation algorithms for lambda_c(Tree_Delta) < lambda < lambda_c(Tree_Delta)+epsilon(Delta), unless NP=RP, for some function epsilon(Delta)>0. We remove the upper bound in the assumptions of Sly's result for Delta not equal to 4 and 5, that is, we show that there does not exist efficient randomized approximation algorithms for all lambda>lambda_c(Tree_Delta) for Delta=3 and Delta>= 6. Sly's inapproximability result uses a clever reduction, combined with a second-moment analysis of Mossel, Weitz and Wormald which prove torpid mixing of the Glauber dynamics for sampling from the associated Gibbs distribution on almost every regular graph of degree Delta for the same range of lambda as in Sly's result. We extend Sly's result by improving upon the technical work of Mossel et al., via a more detailed analysis of independent sets in random regular graphs.

**Galanis Andreas**

Computer Science – Computational Complexity

Scientist

**Ge Qing-Qin**

Physics – Condensed Matter – Superconductivity

Scientist

**Stefankovic Daniel**

Biology – Quantitative Biology – Populations and Evolution

Scientist

**Vigoda Eric**

Biology – Quantitative Biology – Populations and Evolution

Scientist

**Yang Linji**

Mathematics – Probability

Scientist

No associations

LandOfFree

If you have personal experience with

Improved Inapproximability Results for Counting Independent Sets in the Hard-Core Modeldoes not yet have a rating. At this time, there are no reviews or comments for this scientific paper.Improved Inapproximability Results for Counting Independent Sets in the Hard-Core Model, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Improved Inapproximability Results for Counting Independent Sets in the Hard-Core Model will most certainly appreciate the feedback.

Profile ID: LFWR-SCP-O-192492

Use Google custom search:

All data on this website is collected from public sources.
Our data reflects the most accurate information available at the time of publication.