Improved inapproximability results for counting independent sets in the hard‐core model1. Issue 1 (27th December 2012)

• Record Type: Journal Article
• Authors: Galanis, Andreas; Ge, Qi; Štefankovič, Daniel; Vigoda, Eric; Yang, Linji
• Is Part Of: Random structures & algorithms. Volume 45:Issue 1(2014)
• Page Start: 78
• Page End: 110
• Publication Date: 2012-12-27
• Subjects: Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20479
• Languages: English
• ISSNs: 1042-9832

Abstract

<abstract abstract-type="main"> <title>Abstract</title> <p>We study the computational complexity of approximately counting the number of independent sets of a graph with maximum degree Δ. More generally, for an input graph <inline-formula><alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pghmrs4xfx" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:10429832:media:rsa20479:rsa20479-math-0001" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi>G</mml:mi><mml:mo>=</mml:mo><mml:mo stretchy="false">(</mml:mo><mml:mi>V</mml:mi><mml:mo>, </mml:mo><mml:mi>E</mml:mi><mml:mo stretchy="false">)</mml:mo></mml:mrow></mml:math></alternatives></inline-formula> and an activity <inline-formula><alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pghmrs4xdd" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:10429832:media:rsa20479:rsa20479-math-0002" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mo>λ</mml:mo><mml:mo>></mml:mo><mml:mn>0</mml:mn></mml:mrow></mml:math></alternatives></inline-formula>, we are interested in the quantity <inline-formula><alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pghmrs4xcw" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:10429832:media:rsa20479:rsa20479-math-0003" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:msub><mml:mi>Z</mml:mi><mml:mi>G</mml:mi></mml:msub><mml:mo stretchy="false">(</mml:mo><mml:mo>λ</mml:mo><mml:mo stretchy="false">)</mml:mo></mml:mrow></mml:math></alternatives></inline-formula> defined as the sum over independent sets <italic>I</italic> weighted as <inline-formula><alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pghmrs4xbc" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:10429832:media:rsa20479:rsa20479-math-0004" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi>w</mml:mi><mml:mo stretchy="false">(</mml:mo><mml:mi>I</mml:mi><mml:mo stretchy="false">)</mml:mo><mml:mo>=</mml:mo><mml:msup><mml:mo>λ</mml:mo><mml:mrow><mml:mo>|</mml:mo><mml:mi>I</mml:mi><mml:mo>|</mml:mo></mml:mrow></mml:msup></mml:mrow></mml:math></alternatives></inline-formula>. In statistical physics, <inline-formula><alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pghmrs4x9v" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:10429832:media:rsa20479:rsa20479-math-0005" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:msub><mml:mi>Z</mml:mi><mml:mi>G</mml:mi></mml:msub><mml:mo stretchy="false">(</mml:mo><mml:mo>λ</mml:mo><mml:mo stretchy="false">)</mml:mo></mml:mrow></mml:math></alternatives></inline-formula> is the partition function for the hard‐core model, which is an idealized model of a gas where the particles have non‐negligible 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 Δ when Δ is constant and <inline-formula><alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pghmrs4x8b" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:10429832:media:rsa20479:rsa20479-math-0006" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mo>λ</mml:mo><mml:mo><</mml:mo><mml:msub><mml:mo>λ</mml:mo><mml:mi>c</mml:mi></mml:msub><mml:mo stretchy="false">(</mml:mo><mml:msub><mml:mi mathvariant="double-struck">T</mml:mi><mml:mo>Δ</mml:mo></mml:msub><mml:mo stretchy="false">)</mml:mo><mml:mo>:</mml:mo><mml:mo>=</mml:mo><mml:msup><mml:mrow><mml:mo stretchy="false">(</mml:mo><mml:mo>Δ</mml:mo><mml:mo>−</mml:mo><mml:mn>1</mml:mn><mml:mo stretchy="false">)</mml:mo></mml:mrow><mml:mrow><mml:mo>Δ</mml:mo><mml:mo>−</mml:mo><mml:mn>1</mml:mn></mml:mrow></mml:msup><mml:mo>/</mml:mo><mml:msup><mml:mrow><mml:mo stretchy="false">(</mml:mo><mml:mo>Δ</mml:mo><mml:mo>−</mml:mo><mml:mn>2</mml:mn><mml:mo stretchy="false">)</mml:mo></mml:mrow><mml:mo>Δ</mml:mo></mml:msup></mml:mrow></mml:math></alternatives></inline-formula>. The quantity <inline-formula><alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pghmrs4x7t" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:10429832:media:rsa20479:rsa20479-math-0007" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:msub><mml:mo>λ</mml:mo><mml:mi>c</mml:mi></mml:msub><mml:mo stretchy="false">(</mml:mo><mml:msub><mml:mi mathvariant="double-struck">T</mml:mi><mml:mo>Δ</mml:mo></mml:msub><mml:mo stretchy="false">)</mml:mo></mml:mrow></mml:math></alternatives></inline-formula> is the critical point for the so‐called uniqueness threshold on the infinite, regular tree of degree Δ. On the other side, Sly proved that there does not exist efficient (randomized) approximation algorithms for <inline-formula><alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pghmrs4x69" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:10429832:media:rsa20479:rsa20479-math-0008" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:msub><mml:mo>λ</mml:mo><mml:mi>c</mml:mi></mml:msub><mml:mo stretchy="false">(</mml:mo><mml:msub><mml:mi mathvariant="double-struck">T</mml:mi><mml:mo>Δ</mml:mo></mml:msub><mml:mo stretchy="false">)</mml:mo><mml:mo><</mml:mo><mml:mo>λ</mml:mo><mml:mo><</mml:mo><mml:msub><mml:mo>λ</mml:mo><mml:mi>c</mml:mi></mml:msub><mml:mo stretchy="false">(</mml:mo><mml:msub><mml:mi mathvariant="double-struck">T</mml:mi><mml:mo>Δ</mml:mo></mml:msub><mml:mo stretchy="false">)</mml:mo><mml:mo>+</mml:mo><mml:mo>ε</mml:mo><mml:mo stretchy="false">(</mml:mo><mml:mo>Δ</mml:mo><mml:mo stretchy="false">)</mml:mo></mml:mrow></mml:math></alternatives></inline-formula>, unless <inline-formula><alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pghmrs4x5s" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:10429832:media:rsa20479:rsa20479-math-0009" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mtext>NP</mml:mtext><mml:mo>=</mml:mo><mml:mtext>RP</mml:mtext></mml:mrow></mml:math></alternatives></inline-formula>, for some function <inline-formula><alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pghmrs4xgf" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:10429832:media:rsa20479:rsa20479-math-0010" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mo>ε</mml:mo><mml:mo stretchy="false">(</mml:mo><mml:mo>Δ</mml:mo><mml:mo stretchy="false">)</mml:mo><mml:mo>></mml:mo><mml:mn>0</mml:mn></mml:mrow></mml:math></alternatives></inline-formula>. We remove the upper bound in the assumptions of Sly's result for <inline-formula><alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pghmrs4xq2" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:10429832:media:rsa20479:rsa20479-math-0011" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mo>Δ</mml:mo><mml:mo>≠</mml:mo><mml:mn>4</mml:mn><mml:mo>, </mml:mo><mml:mn>5</mml:mn></mml:mrow></mml:math></alternatives></inline-formula>, that is, we show that there does not exist efficient randomized approximation algorithms for all <inline-formula><alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pghmrs4xpj" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:10429832:media:rsa20479:rsa20479-math-0012" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mo>λ</mml:mo><mml:mo>></mml:mo><mml:msub><mml:mo>λ</mml:mo><mml:mi>c</mml:mi></mml:msub><mml:mo stretchy="false">(</mml:mo><mml:msub><mml:mi mathvariant="double-struck">T</mml:mi><mml:mo>Δ</mml:mo></mml:msub><mml:mo stretchy="false">)</mml:mo></mml:mrow></mml:math></alternatives></inline-formula> for <inline-formula><alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pghmrs4xs3" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:10429832:media:rsa20479:rsa20479-math-0013" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mo>Δ</mml:mo><mml:mo>=</mml:mo><mml:mn>3</mml:mn></mml:mrow></mml:math></alternatives></inline-formula> and <inline-formula><alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pghmrs4xrk" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:10429832:media:rsa20479:rsa20479-math-0014" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mo>Δ</mml:mo><mml:mo>≥</mml:mo><mml:mn>6</mml:mn></mml:mrow></mml:math></alternatives></inline-formula>. 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 Δ for the same range of λ 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. © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 45, 78–110, 2014</p> </abstract>