On counting independent sets in sparse graphs

Martin Dyer^{∗} University of Leeds United Kingdom

Alan Frieze^{†} Carnegie Mellon University U.S.A.

Mark Jerrum^{‡} University of Edinburgh United Kingdom

July 16, 1998

Abstract We prove two results concerning approximate counting of independent sets in graphs with constant maximum degree Δ. The first implies that the Monte Carlo Markov chain technique is likely to fail if Δ ≥ 6. The second shows that no fully polynomial randomized approximation scheme can exist if Δ ≥ 25, unless RP = NP.

∗School of Computer Studies, University of Leeds, LS2 9JT, United Kingdom (dyer@scs.leeds.ac.uk). Supported by ESPRIT Working Group RAND2.

†Department of Mathematics, Carnegie Mellon University, Pittsburgh, PA 15213, U.S.A.

(af1p+@andrew.cmu.edu).

‡Department of Computer Science, University of Edinburgh, EH9 3JZ, United Kingdom (mrj@dcs.ed.ac.uk). Supported by ESPRIT Working Group RAND2.

1 Introduction

Counting independent sets in graphs is one of several combinatorial counting problems which have received recent attention. The problem is known to be #Pcomplete, even for low degree graphs [3]. On the other hand, it has been shown that, for graphs of maximum degree Δ = 4, randomized approximate counting is possible [7, 3]. This success has been achieved using the Monte Carlo Markov chain method to construct a fully polynomial randomized approximation scheme (fpras). This has led to a natural question as to how far this success might extend.

Here we consider in more detail this question of counting independent sets in graphs with constant maximum degree. We prove two results. The first, in Section 2, shows that the Monte Carlo Markov chain method is likely to fail for graphs with Δ = 6. This leaves open only the case Δ = 5.

Our second result gives an explicit value of Δ above which approximate counting, using any kind of polynomial-time algorithm, is impossible unless RP = NP. The bound we obtain is Δ = 25, though we suspect that the true value is in single figures, probably 6.

We note that Berman and Karpinski [2] have recently given new explicit bounds for the approximation ratio for the maximum independent set and other problems in low-degree graphs. These directly imply an inapproximability result for counting. (See [7].) However, the bound on Δ obtained this way is larger than ours by at least two orders of magnitude.

2 Monte Carlo Markov chains

For a graph G, let I(G) denote the collection of independent sets of G. Let M(G) be any Markov chain, asymptotically uniform on I(G), with transition matrix P_{G}. In this section G will be a bipartite graph with a vertex bipartition into classes of equal size n. Let b(n) ≤ n be any function of n and suppose we have P_{G}(σ_{1}, σ_{2}) = 0 whenever |σ_{1} ⊕ σ_{2}| > b(n), where ⊕ denotes symmetric difference. We will say that M(G) is b(n)-cautious. Thus a b(n)-cautious chain is not permitted to change the status of more than b(n) of the vertices in G at any step. Ideally, we would wish to have b(n) a constant (as in [7, 3]). However, we will show that no b(n)-cautious chain on I(G) can mix rapidly unless b(n) = Ω(n). Thus any chain which does mix rapidly on M(G) must change the status of a sizeable proportion of the vertices at each step.

Specifically, we prove the following

Theorem 1 Let Δ ≥ 6 and b(n) ≤ 0.35n. Then there exists a bipartite graph G_{0}, of maximum degree Δ, on n + n vertices (more precisely a sequence of such graphs parameterised by n) with the following property: for any b(n)-cautious Markov chain on I(G_{0}), and almost every (in the uniform measure) choice of starting state, the mixing time is Ω(e^{γn}), for some constant γ > 0.

Since, of course, there does exist an n-cautious chain which mixes rapidly, our result cannot be strengthened much further. The remainder of this section is devoted to the proof of Theorem 1.

We infer the existence of the graph G_{0} by random graph methods. Let K_{n,n} denote the complete bipartite graph with vertex bipartition V_{1}, V_{2}, where |V_{1}| = |V_{2}| = n, and let G be the union of Δ perfect matchings selected independently and uniformly at random in K_{n,n}. (Since the perfect matchings are independent, they may well share some edges.) Denote by G(n, n, Δ) the probability space of bipartite graphs G so defined. Where no confusion can arise, we simply write G for this class below. Note that G is a class of graphs with degree bound Δ.

Let 0 < α, β < 1 be chosen values. For G ∈ G, we consider the collection I_{G}(α, β) of σ ∈ I(G) such that |σ ∩ V_{1}| = αn and |σ ∩ V_{2}| = βn. (We assume that αn, βn are integers, merely to ease exposition.) We will call σ ∈ I_{G}(α, β) an (α, β)-set. Using linearity of expectation, we may easily compute the expected number E(α, β) = E(|I_{G}(α, β)|) of (α, β)-sets in G: it is just the number of ways of choosing an αn-subset from V_{1} and a βn-subset from V_{2}, multiplied by the probability that all Δ perfect matchings avoid connecting the αn-subset to the βn-subset. Thus,

E(α, β) = \binom{n}{αn}\binom{n}{βn} [\binom{(1 − β)n}{αn}/\binom{n}{αn}]^{Δ}

= (\frac{(1 − β)^{(Δ−1)(1−β)}(1 − α)^{(Δ−1)(1−α)}}{α^{α}β^{β}(1 − α − β)^{Δ(1−α−β)}} )^{n(1+o(1))}

= e^{ϕ(α,β)n(1+o(1))},  (1)

where

ϕ(α, β) = −α ln α − β ln β − Δ(1 − α − β) ln(1 − α − β)
+ (Δ − 1)((1 − α) ln(1 − α) + (1 − β) ln(1 − β)). (2)

It follows that

\frac{∂ϕ}{∂α} = − ln α − (Δ − 1) ln(1 − α) + Δ ln(1 − α − β),  (3)
\frac{∂ϕ}{∂β} = − ln β − (Δ − 1) ln(1 − β) + Δ ln(1 − α − β),  (4)
\frac{∂^{2}ϕ}{∂α^{2}} = −\frac{1}{α} + \frac{Δ − 1}{1 − α} − \frac{Δ}{1 − α − β} ,  (5)
\frac{∂^{2}ϕ}{∂β^{2}} = −\frac{1}{β} + \frac{Δ − 1}{1 − β} − \frac{Δ}{1 − α − β} ,  (6)
\frac{∂^{2}ϕ}{∂α ∂β} = −\frac{Δ}{1 − α − β} .  (7)

Now ϕ is defined on the triangle

T = {(α, β) : α, β ≥ 0, α + β ≤ 1},

and is clearly symmetrical in α, β. (The function ϕ is defined by equation (2) on the interior of T , and can be extended to the boundary by taking limits.) Moreover, using (3)–(7), the following facts are established in Appendix A about the stationary points of ϕ on T :

(i) The function ϕ has no local minima, and no local maxima on the boundary of T .

(ii) All local maxima of ϕ satisfy α + β + Δ(Δ − 2)αβ ≤ 1.

(iii) If Δ ≤ 5, ϕ has only a single local maximum, which is on the line α = β.

(iv) If Δ ≥ 6, ϕ has exactly two local maxima, symmetrical in α,β and a single saddle-point on α = β.

From (iii) and (iv), we see that the distribution of the numbers of (α, β)-sets undergoes a dramatic change from Δ = 5 to Δ = 6. For Δ ≤ 5, the “typical” (α, β)-set is “balanced” (i.e. has α ≈ β), whereas for Δ ≥ 6 it is “unbalanced”. We will examine the first unbalanced case, Δ = 6, and make this precise.

We may determine numerically (see Appendix A) that the maximum of ϕ with smaller α occurs at (α^{∗}, β^{∗}) ≈ (0.03546955, 0.40831988), and there is a c ≥ 0.71513499 such that ϕ(α^{∗}, β^{∗}) > c. Therefore let us say (α, β) is a middle point if |β −α| ≤ 0.35, and an (α, β)-set is a middle set if (α, β) is a middle point. Let ϕ_{mid} denote the maximum of ϕ(α, β) for (α, β) a middle point. Then, since by (iv) ϕ_{mid} is attained on |β − α| = 0.35, further numerical computation shows that there is a constant γ ≥ 0.00018191 such that ϕ_{mid} < c − γ. Hence we have shown that, for large enough n

E^{∗} = E(α^{∗}, β^{∗}) > exp(cn),

and

E_{mid} = ∑_{|β−α|≤0.35} E(α, β) < n^{2} exp(ϕ_{mid}n) < exp((c − γ)n).

Thus E_{mid} < e^{−γn}E^{∗}. For G ∈ G, let X^{∗} denote the number of (α^{∗}, β^{∗})-sets G possesses and X_{mid} its number of middle sets. Then

E(X_{mid} − e^{−γn}X^{∗}) = E_{mid} − e^{−γn}E^{∗} < 0.

Thus, for large enough n, there must exist a G_{0} ∈ G such that

X_{mid}(G_{0}) < e^{−γn}X^{∗}(G_{0}).  (8)

This is the graph G_{0} of Theorem 1, and the remainder of our argument concerns G_{0}. Note that we have only shown the existence of G_{0}, We cannot assert from the above that a random graph in G is likely to satisfy (8), though more delicate arguments might well establish this.

Now consider a 0.35n-cautious chain M(G_{0}) = M_{0}, on I(G_{0}). We will examine the conductance [6], Φ(M_{0}), of M_{0}. To this end, let S comprise all (α, β)-sets with α ≥ β, i.e.

S = {σ ∈ I(G_{0}) : |σ ∩ V_{1}| ≥ |σ ∩ V_{2}|}.

Then, if P_{0} is the transition matrix of M_{0},

∑_{σ_{1}∈S} ∑_{σ_{2}∉S} P_{0}(σ_{1}, σ_{2}) < X_{mid}(G_{0}),  and |S| > X^{∗}(G_{0}).  (9)

It follows from (9) that

Φ(M_{0}) < e^{−γn}.

Now, suppose the chain is started at a state chosen uniformly in S. By symmetry this is equivalent to choosing a set uniformly from I(G_{0}). Then, as shown by Jerrum [5], the probability that the chain is still in S after t steps is at least (1 − Φ)^{t}. Hence the variation distance of the chain from the uniform distribution is at least (1 − Φ)^{t} − \frac{1}{2}. It follows, by a simple calculation, that if n ≥ 1/γ, the mixing time (i.e. the time to reach variation distance e^{−1}) is at least 0.0895e^{γn}.

3 Hardness of approximate counting

The result of the previous section implies that the usual approach to approximating the number of independent sets in a low-degree graph must fail when Δ ≥ 6, at least in the worst case. Here we show that, if the degree bound is somewhat larger, then any approach to approximating the number of independent sets is doomed to failure, under a reasonable complexity assumption. Precisely, the remainder of this section is devoted to proving the following

Theorem 2 Unless NP = RP, there is no polynomial time algorithm which estimates the logarithm of the number of independent sets in a Δ-regular graph (Δ ≥ 25) within relative error at most ϵ = 10^{−6}.

We give a randomized reduction from the following problem E2LIN2, analysed by Håstad [8]. The input is a system A of m equations over Z_{2} in n variables x_{1}, x_{2}, …, x_{n}, such that each equation has exactly two variables. (Thus each equation is of the form x_{i} + x_{j} = 0 or x_{i} + x_{j} = 1.) The objective is to find a maximum cardinality consistent subset of equations in A, i.e., to assign values to the variables so as to maximize the number m_{C} of satisfied equations. Håstad showed, using the powerful theory of PCP, that (unless NP = RP) there is no polynomial time algorithm which can estimate m_{C} within any constant factor smaller than 12/11.

Therefore consider an instance A of E2LIN2, as above. We will construct (by a randomized algorithm) a graph G = (V, E), regular of degree Δ. We then show that, if we can approximate the logarithm of the number of independent sets in G to within the required relative error, we can (with high probability) approximate the size of m_{C} in A, to within a factor 12/11 − ϵ. Theorem 2 will then follow.

Let us write [n] = {1, 2, …, n}. We construct the graph G = G(A) as follows. We assume m ≥ n, otherwise A is decomposable or consistent. Let M = m^{6} and, for each i ∈ [n], let A_{i} be the multiset of equations containing x_{i}, with (multiset) cardinality d_{i}. We represent x_{i} by a regular bipartite graph H_{i} = (L_{i}, R_{i}, F_{i}) of degree δ = Δ − 1. Here L_{i} = ⋃_{a∈A_{i}} L_{i,a}, R_{i} = ⋃_{a∈A_{i}} R_{i,a} where the sets L_{i,a}, R_{i,a} partition L_{i} and R_{i} respectively, and for all i, a, |L_{i,a}| = |R_{i,a}| = M. Thus H_{i} is bipartite with both its vertex sets of size Md_{i}. Later, we will associate L_{i} with the assignment x_{i} = 0, and R_{i} with x_{i} = 1.

The graph H_{i} = (L_{i}, R_{i}, F_{i}) will be sampled from G(Md_{i}, Md_{i}, δ), where G is the class of random graphs defined in section 2. Here, however, we will reject graphs which are not δ-regular. It is known [1] that a graph in G is regular of full degree with constant probability (for constant δ). Moreover, the property of being δ-regular can clearly be checked in polynomial time.

The equations a of A determine the edges connecting the H_{i} in G, as follows. If a is the equation x_{i} + x_{j} = 1 (x_{i} + x_{j} = 0 resp.), we add an arbitrary perfect matching between L_{i,a} and L_{j,a} (R_{j,a} resp.) and another between R_{i,a} and R_{j,a} (L_{j,a} resp.). Thus G is a regular graph of degree Δ. We will show that approximating the logarithm of the number of independent sets in G to within a factor (1 + 10^{−6}) will allow us to approximate the E2LIN2 instance within the Håstad bound.

Before returning to the issue of approximation, we will need to establish some crucial properties of the “typical” independent set in G. For this purpose, let I be sampled uniformly from I(G). First we show that I “occupies about half the available space” in each L_{i,a} or R_{i,a}.

Let L_{i,a} be the set of vertices in L_{i,a} with no neighbour in I and let L_{i} = ⋃_{a∈A_{i}} L_{i,a}.

Lemma 1 Then, except for probability e^{−Ω(m^{2})}, either |L_{i,a}| < m^{4} or |L_{i,a}| = (2 + O(1/m))|I ∩ L_{i,a}|.

Proof If we condition on I ∩ (V \ L_{i,a}) then I ∩ L_{i,a} is a random subset of L_{i,a}. If |L_{i,a}| ≥ m^{4} then Chernoff’s bound implies that

Pr(|I ∩ L_{i,a}| ∉ \frac{1}{2}(1 ± \frac{1}{m})|L_{i,a}|) ≤ 2 exp ( − \frac{1}{3}m^{2}),

from which the Lemma follows. □

Clearly we may define R_{i,a} and R_{i} symmetrically and prove an analogous result. It is also clear that we may claim the Lemma for all i, a since there are less than m^{2} such pairs. We now deduce that at least around half of L_{i} is “available” to I in H_{i}, if we fix I outside H_{i}.

Let L′_{i} be the set of vertices in L_{i} with no neighbour in I outside of H_{i}.

Lemma 2 Except for probability e^{−Ω(m^{2})}, |L′_{i}| ≥ (\frac{1}{2} − O(1/m))|L_{i}|.

Proof We condition on the whole of I outside of H_{i}. If L_{i,a} is joined by a matching to V_{j,a} (V ∈ {L, R}) then, from Lemma 1, M ≥ (2 + O(1/m))|I ∩ V_{j,a}|. Hence

|\{v ∈ L_{i,a} : \{v, w\} ∈ E \ F_{i} implies w ∉ I\}| ≥ (\frac{1}{2} − O(1/m))|L_{i,a}|.

Summing this over all a ∈ A_{i} gives the Lemma. □

Again, we may define R′_{i} and prove a corresponding result. We now show, that for each i either |L_{i}| or |R_{i}| is “small”. We will temporarily drop the suffix i, and write H rather than H_{i} etc. Let N = |L| = dM ≤ m^{7}, a = |L′|/N, b = |R′|/N. Without loss of generality, we assume a ≥ b and, from Lemma 2, b ≥ \frac{1}{2} − O(1/m). Write σ = I ∩ H, where I is a uniformly chosen independent set in G. We will say that σ is an (α, β)-set if |σ ∩ L| = αaN, |σ ∩ R| = βbN. Note that, while we treat α, β as continuous, there are in fact at most N values for each of a, b, αa, βb (and hence N^{2} values of each of α, β).

Lemma 3 Let δ ≥ 24. If I is a uniformly chosen independent set in G then, except for probability e^{−Ω(m^{2})}, min(|L_{i}|, |R_{i}|) ≤ λN, where λ = 0.00943 .

Proof We argue conditionally on L′, R′. It is easy to see that there are at least 2^{aN} independent sets in H. We will show that, for α, β not satisfying the condition of the Lemma, the number of (α, β)-sets is so much smaller than this that they appear with probability e^{−Ω(m^{2})}. It will be sufficient to show that the expected number of (α, β)-sets in such a case is 2^{aN−Ω(m^{2})}, since Markov’s inequality will then imply the inequality for the actual number. Moreover, it will be sufficient to prove this for any particular triple H, α, β, since there can be at most N^{4n} = e^{O(m ln m)} different combinations of values of α, β in the whole of G. Now the expected number of (α, β)-sets in H is

E(α, β) = \binom{aN}{αaN}\binom{bN}{βbN} [\binom{(1 − bβ)N}{αaN}/\binom{N}{αaN}]^{δ}

≤ \binom{aN}{αaN}\binom{bN}{βbN}(1 − bβ)^{αaδN}

≤ [(α^{α}(1 − α)^{(1−α)})^{−a} (β^{β}(1 − β)^{(1−β)})^{−b} e^{−αβabδ}]^{N(1+o(1))}

= e^{ψ(α,β)N(1+o(1))},  (10)

where

ψ(α, β) = −a(α ln α + (1 − α) ln(1 − α)) − b(β ln β + (1 − β) ln(1 − β)) − αβabδ. (11)

It follows that

\frac{∂ψ}{∂α} = a(− ln α + ln(1 − α) − βbδ),  \frac{∂ψ}{∂β} = b(− ln β + ln(1 − β) − αaδ), (12)

\frac{∂^{2}ψ}{∂α^{2}} = \frac{−a}{α(1 − α)},  \frac{∂^{2}ψ}{∂β^{2}} = \frac{−b}{β(1 − β)},  \frac{∂^{2}ψ}{∂α ∂β} = −abδ.  (13)

The following two facts about ψ are easily verified.

ψ(α, β) ≥ ψ(1 − α, β) if α ≤ \frac{1}{2}  (14)
ψ(α, β) ≥ ψ(α, 1 − β) if β ≤ \frac{1}{2}  (15)
ψ(α, β) ≥ ψ(β, α)  if β ≤ α ≤ 1 − β  (16)

We wish to determine the regions where ψ ≥ a ln 2. These are connected neighbourhoods of the local maxima of ψ. From (12) we see that ψ has no boundary maxima for α, β in the unit square U. Thus, from (13), ψ has only local maxima or saddle-points in U, and a stationary point is a local maximum if and only if

α(1 − α)β(1 − β) ≤ 1/(abδ^{2}).  (17)

Thus, at any local maximum, either β(1 − β) ≤ 1/(bδ) or α(1 − α) ≤ 1/(aδ). If the former, this and bδ ≥ 12 − o(1) imply β < .1, and hence β < 1.2/bδ. An identical argument holds for α. Let us denote the rectangle [ℓ_{α}, u_{α}] × [ℓ_{β}, u_{β}] by [ℓ_{α}, u_{α} | ℓ_{β}, u_{β}]. Thus any local maximum of ψ must lie in either [0, 1 | 0, 1.2/bδ] or [0, 1.2/aδ | 0, 1]. In [0, 1.2/bδ | 0, 1.2/bδ], α, β < 0.1 and hence

ψ(α, β) < 2a(−0.1 ln(0.1) − 0.9 ln(0.9)) < a ln 2.

Then, from (14) and (15), we also have ψ(α, β) < a ln 2 in [1−1.2/bδ, 1 | 0, 1.2/bδ] and [0, 1.2/bδ | 1 − 1.2/bδ, 1]. Now, if β ≤ 1.2/bδ, let ρ = 1 − 2α and consider the upper bound

ψ(α, β) ≤ Ψ(ρ, β) = a(ln 2 − \frac{1}{2}ρ^{2}) + bβ(1 − ln β) − \frac{1}{2}(1 − ρ)βabδ.  (18)

For fixed β, it is easily shown that Ψ is maximized if ρ = \frac{1}{2}bδβ < 0.6. If bδβ = 1.2, then ρ = 0.6 and

max_{ρ} Ψ(ρ, β) ≤ a(ln 2 − 0.18) + 0.1a(1 − ln(0.1)) − 0.24a < a ln 2.

Thus ψ < a ln 2 everywhere on the boundary of [1.2/bδ, 1 − 1.2/bδ | 0, 1.2/bδ] (but not including the shared boundary with U). Hence, by (16), ψ < a ln 2 everywhere on the boundary of [0, 1.2/bδ | 1.2/bδ, 1 − 1.2/bδ], which contains [0, 1.2/aδ | 1.2/bδ, 1 − 1.2/bδ]. Moreover ψ(α, β) ≥ ψ(β, α) for all points (α, β) in [1.2/bδ, 1 − 1.2/bδ | 0, 1.2/bδ]. It follows that it is sufficient to determine β^{∗} such that ψ(α, β^{∗}) < a ln 2 everywhere in [1.2/bδ, 1 − 1.2/bδ | β^{∗}, 1.2/bδ]. To this end again consider

Ψ_{0}(β) = max_{ρ} Ψ(ρ, β) = a ln 2 + bβ(1 − ln β) − \frac{1}{2}abβδ + \frac{1}{8}ab^{2}β^{2}δ^{2}.

Now Ψ_{0} < a ln 2 if

bβδ^{2} − 4δ + 8(1 − ln β)/a < 0.

This inequality is satisfied provided

2 (1 − \sqrt{1 − 2bβ(1 − ln β)/a}) < bβδ < 2 (1 + \sqrt{1 − 2bβ(1 − ln β)/a}) .

The right hand inequality is clearly irrelevant since we are assuming β ≤ 1.2/bδ. Thus we need only consider the left hand inequality, i.e. for fixed γ = bβ < 1.2/δ, we require

γδ > max_{\frac{1}{2} −o(1)≤b≤a≤1} 2 (1 − \sqrt{1 − 2γ(1 − ln γ + ln b)/a}) .

Considering first b, the maximum occurs when b = a. So we have

γδ > max_{\frac{1}{2} −o(1)≤a≤1} 2 (1 − \sqrt{1 − 2γ(1 − ln γ + ln a)/a}) .

But, since a ≥ γ, the maximum now occurs when a = \frac{1}{2}. Thus we require

γδ > 2 (1 − \sqrt{1 − 4γ(1 − ln γ − ln 2)}) .

To achieve γ = 0.004715, we require δ ≥ 23.3.

Thus we have shown that min(aα, bβ) < 0.004715. The conclusion now follows immediately from Lemma 1. □

We now establish the relationship between the number of independent sets in Γ and the maximum size of a consistent subset of A. Let I = I(G). For σ ∈ I let S_{σ} ⊆ [n] be defined by

S_{σ} = {i : |L_{i} ∩ σ| > |R_{i} ∩ σ|, i ∈ [n]}.

For S ⊆ [n] let I_{S} = {σ ∈ I : S_{σ} = S} and let μ_{S} = |I_{S}|. Recall that m is the number of equations in A.

Lemma 4 For S ⊆ [n], let θ(S) be the number of equations in A satisfied by the assignment x_{i} = 1 (i ∈ S), x_{i} = 0 (i ∉ S). Then

4^{Mθ(S)}3^{M(m−θ(S))} ≤ μ_{S} ≤ 4^{Mθ(S)}3^{M(m−θ(S))}2^{2λmM}(1 + o(1)),  (19)

where λ is as in Lemma 3.

Proof Fix S ⊆ [n] and for σ ∈ I_{S} we let J_{σ} = σ ∩ (⋃_{i∈S} L_{i} ∪ ⋃_{i∉S} R_{i}). Informally, J_{σ} restricts σ to the left or right of each subgraph H_{i}, according to which side contains the larger part of σ. Let

μ̂_{S} = |{J_{σ} : σ ∈ I_{S}}| ≤ μ_{S}.

We show that

μ̂_{S} = 4^{Mθ(S)}3^{M(m−θ(S))}.  (20)

This immediately proves the lower bound in (19). Furthermore, Lemma 1 implies that for a fixed value J of J_{σ} there are (up to a factor (1 + e^{−Ω(m^{2})}) at most

∏_{i∈[n]} 2^{λd_{i}M} = 2^{λM ∑_{i} d_{i}} = 2^{2λmM}

sets σ ∈ I_{S} with J_{σ} = J. The upper bound then follows.

To prove (20) we consider the number of possible choices for J ∩ L_{i,a}, J ∩ R_{i,a}, J ∩ L_{j,a} and J ∩ R_{j,a} for every equation a : x_{i} + x_{j} = z_{a} (z_{a} ∈ {0, 1}). For given S, let us define

X_{i,a} = \begin{cases}L_{i,a}, & if i ∈ S; \\ R_{i,a}, & if i ∉ S. \end{cases}

Then there are two cases, determined by the status of a.

(1) Equation a is satisfied by the assignment derived from S. Then there are 2^{M} choices for each of J ∩ X_{i,a}, J ∩ X_{j,a}, giving 4^{M} in all.

(2) Equation a is not satisfied by the assignment derived from S. Then the subgraph of G induced by X_{i,a} ∪ X_{j,a} is a matching of size M, and hence contains 3^{M} independent sets.

Multiplying the estimates from the two cases over all a ∈ A proves (20) and the Lemma. □

We now proceed to the proof of Theorem 2. Let Z_{I} = Z_{I}(G) denote the logarithm of the number of independent sets of G(A). Let Z_{C} = Z_{C}(A) denote the maximum number of consistent equations in A.

Let Y_{I} be some estimate of Z_{I} satisfying |Y_{I}/Z_{I} − 1| ≤ ϵ = 10^{−6}. Using Y_{I} we define

Y_{C} = (\frac{Y_{I}}{M} − m ln 3) \frac{1 + 10^{−5}}{ln(4/3)} .

A simple calculation will then show that 1 ≤ Y_{C}/Z_{C} ≤ 12/11 − ϵ, so that Y_{C} determines Z_{C} with sufficient accuracy to beat the approximability bound for E2LIN2.

From Lemma 4 we see that

Y_{I} ≥ (1 − ϵ)M(Z_{C} ln(4/3) + m ln 3).

Hence, since Z_{C} ≥ m/2,

Y_{C}/1.00001 ≥ (1 − ϵ)Z_{C} − \frac{ϵm ln 3}{ln(4/3)} ≥ Z_{C} (1 − \frac{ϵ ln 12}{ln(4/3)}) ≥ 0.999991Z_{C},

which implies Y_{C} ≥ Z_{C}. On the other hand Lemma 4 also implies that

Y_{I} ≤ (1 + ϵ)[M(Z_{C} ln(4/3) + m ln 3 + 2mλ ln 2) + n ln 2],

where λ ≤ 0.00943. Hence

Y_{C}/1.00001 ≤ (1 + ϵ)Z_{C} + \frac{ϵm ln 3}{ln(4/3)} + \frac{(1 + ϵ)2mλ ln 2}{ln(4/3)} + \frac{(1 + ϵ) ln 2}{n ln(4/3)}
≤ Z_{C} (1 + ϵ + \frac{ϵ ln 6}{ln(4/3)} + \frac{4 ln 2(1 + ϵ)λ}{ln(4/3)} + O (\frac{1}{n^{2}} ))
≤ Z_{C} (1.0908907 + O (\frac{1}{n^{2}} )) ,

which implies Y_{C}/Z_{C} ≤ 12/11 − ϵ for n large enough.

References

[1] E. A. Bender. The asymptotic number of non-negative integer matrices with given row and column sums. Discrete Mathematics, 10:217–223, 1974.

[2] Piotr Berman and Marek Karpinski. On some tighter inapproximability results, 1998. (Preprint.)

[3] Martin Dyer and Catherine Greenhill. On Markov chains for independent sets, 1997. (Preprint.)

[4] Mark Jerrum, Leslie Valiant and Vijay Vazirani. Random generation of combinatorial structures from a uniform distribution. Theoretical Computer Science, 43:169–188, 1986.

[5] Mark Jerrum. Large cliques elude the Metropolis process. Random Structures and Algorithms, 3:347–359, 1992.

[6] Mark Jerrum and Alistair Sinclair. The Markov chain Monte Carlo method: an approach to approximate counting and integration. In Dorit Hochbaum, editor, Approximation Algorithms for NP-Hard Problems, pages 482–520. PWS Publishing, Boston, 1996.

[7] Michael Luby and Eric Vigoda. Approximately counting up to four. In Proceedings of the Twenty-Ninth Annual ACM Symposium on Theory of Computing, pages 682–687. ACM Press, 1997.

[8] Johann Håstad. Some optimal inapproximability results. In Proceedings of the Twenty-Ninth Annual ACM Symposium on Theory of Computing, pages 1–10. ACM Press, 1997.

Appendix A

We prove the claims made in Section 2 concerning the function ϕ.

(i) From (5), it can easily be checked that ∂^{2}ϕ/∂α^{2} < 0 on the interior of T , and hence ϕ can have no interior local minima. On α = 0, ϕ has a maximum at β = \frac{1}{2} using (4), but then from (3) we find ∂ϕ/∂α = +∞ at α = 0, β = \frac{1}{2}. Similarly β = 0. On α + β = 1, both ∂ϕ/∂α, ∂ϕ/∂β = −∞, so ϕ can have no maximum.

(ii) Since both ∂^{2}ϕ/∂α^{2}, ∂^{2}ϕ/∂β^{2} < 0, ϕ has a maximum if and only if the Hessian of ϕ has positive determinant. The condition for this is α + β + Δ(Δ − 2)αβ ≤ 1, as may be checked from (5)–(7).

(iii) From (3) and (4), the conditions for a stationary point of ϕ may be written

β = f(α), α = f(β),

where

f(x) = 1−x−x^{1/Δ}(1−x)^{1−1/Δ} = (1−x) [1 − (\frac{x}{1 − x})^{1/Δ}] (0 ≤ x ≤ 1).

Thus at any stationary point

α = f(f(α)).  (21)

Clearly f(x) ≤ 0 for x ≥ \frac{1}{2}, so α < \frac{1}{2} at any stationary point. Similarly β < \frac{1}{2}. To study the roots of (21), the change of variable y = (α/(1−α))^{1/Δ} proves convenient. With a little calculation we may express α, f(α), and f(f(α)) in terms of y:

α = \frac{y^{Δ}}{1 + y^{Δ}}
f(α) = (1 − α)(1 − y) = \frac{1 − y}{1 + y^{Δ}}

and

f(f(α)) = (1 − f(α)) − (f(α)(1 − f(α))^{Δ−1})^{1/Δ}

= (α + \frac{y}{1 + y^{Δ}} ) − \frac{1}{1 + y^{Δ}} ((1 − y)(y + y^{Δ})^{Δ−1})^{1/Δ}

= α + \frac{y}{1 + y^{Δ}} [1 − (\frac{(1 − y)(1 + y^{Δ−1})^{Δ−1}}{y} )^{1/Δ}];

so that (21) is equivalent to

(1 + y^{Δ−1})^{Δ−1} = \frac{y}{1 − y}  (0 ≤ y < 1).  (22)

Note that the implicit mapping from α to y is a bijection, so we may legitimately study the solution set of (21) through that of (22). Note also that (22) has a root y′ satisfying y + y^{Δ} = 1, and this exists for any Δ > 0. The reader may check that y + y^{Δ} = 1 is equivalent to α = f(α), and thus y′ satisfies α = β. To analyse (22) in general, let

g(y) = (Δ − 1) ln(1 + y^{Δ−1}) + ln(1 − y) − ln y,

so g(y) = 0 has the same roots as (22). Then one may check that g′(y) = 0 if and only if

h(y) =^{def} Δ(Δ − 2)y^{Δ−1} − (Δ − 1)^{2}y^{Δ} − 1 = 0.

But h(0) = −1, h(1) = −2, and h has a single maximum on [0, 1] at y′′ = (Δ − 2)/(Δ − 1). Now h(y′′) = (Δ − 2)^{Δ}/(Δ − 1)^{Δ−1} − 1 > 0 if and only if Δ ≥ 6, and h(y′′) < 0 otherwise. Therefore h has two roots in [0, 1] if Δ ≥ 6, otherwise no roots.. Thus g has a single root in [0, 1] if Δ ≤ 5, otherwise at most three roots. In the latter case, however, g(0) = +∞, g(1) = −∞, g(y′) = 0 and a simple calculation shows

g′(y′) = \frac{(Δ − 1)^{2}(1 − y′)^{2} − 1}{y′(1 − y′)} > 0

if and only if Δ ≥ 6, and g′(y′) < 0 otherwise. These facts imply that g has exactly three roots if Δ ≥ 6.

Now the reader may check that the point (α′, α′) corresponding to y′ (i.e., given by solving y′ = (α′/(1 − α′))^{1/Δ}) satisfies

α + β + Δ(Δ − 2)αβ ≤ 1, i.e. (\frac{1 − α}{α}) (\frac{1 − β}{β} ) ≥ (Δ − 1)^{2},

if and only if y′ ≥ y′′. This holds if and only if Δ ≤ 5. Thus this point is a maximum for Δ ≤ 5, otherwise a saddle-point.

Thus ϕ has one stationary point in T (on α = β) if Δ ≤ 5, and this is a maximum.

(iv) By the above, if Δ ≥ 6, ϕ has no boundary maximum on T′ = {(α, β) ∈ T : α ≤ β} and therefore has a maximum in the interior of T′ by continuity. By symmetry there is also a maximum in T \ T′. Thus, when Δ ≥ 6, ϕ has two symmetrical maxima and a single saddle-point on the line α = β.