Theory of Computing, Volume 2 (2006), pp. 19–52 http://theoryofcomputing.org

Proving Integrality Gaps without Knowing the Linear Program

Sanjeev Arora^{∗} Béla Bollobás^{†} László Lovász Iannis Tourlakis

Received: June 1, 2005; published: February 3, 2006.

Abstract: Proving integrality gaps for linear relaxations of NP optimization problems is a difficult task and usually undertaken on a case-by-case basis. We initiate a more systematic approach. We prove an integrality gap of 2 − o(1) for three families of linear relaxations for vertex cover, and our methods seem relevant to other problems as well.

ACM Classification: G.1.6, F.1.3

AMS Classification: 68Q17, 90C05, 90C57

Key words and phrases: linear programming, inapproximability, approximation algorithms, NP-hard problems, integrality gaps, lift-and-project, vertex cover

1 Introduction

Approximation algorithms for NP-hard problems—metric tsp, vertex cover, graph expansion, cut problems, etc.—often use a linear relaxation of the problem (see Vazirani [31], Hochbaum [22]). For instance, a simple 2-approximation algorithm for vertex cover solves the following relaxation: minimize ∑_{i∈V} x_{i} such that x_{i} + x_{j} ≥ 1 for all {i,j} ∈ E. One can show that in the optimum solution, x_{i} ∈ {0,1/2,1}. Thus rounding the 1/2’s up to 1 gives a vertex cover [21]. This also proves an upper bound of 2 on the integrality gap of the relaxation, which is the maximum over all graphs G of the ratio of the size of the minimum vertex cover in G and the cost of the optimum fractional solution.

∗Supported by David and Lucile Packard Fellowship, NSF Grants CCR-009818 and CCR-0205594. Work done while visiting Microsoft Research and the CS Dept at UC Berkeley.

†Research supported by NSF grant DSM 9971788 and DARPA grant F33615-01-C-1900 Authors retain copyright to their papers and grant “Theory of Computing” unlimited rights to publish the paper electronically and in hard copy. Use of the article is permitted as long as the author(s) and the journal are properly acknowledged. For the detailed copyright statement, see http://theoryofcomputing.org/copyright.html.

\begin{matrix}c \\ ◯ \end{matrix} 2006 Sanjeev Arora, Béla Bollobás, László Lovász, and Iannis Tourlakis

S. Arora, B. Bollobás, L. Lovász, I. Tourlakis

Can we write a linear relaxation with a lower integrality gap, say 1.5? Note that the LP need not even be of polynomial size so long as it comes with a polynomial time separation oracle, which is all we need to solve it with the Ellipsoid method.

Such quests for tighter relaxations can seem never-ending, since even simple modifications could conceivably tighten the relaxation. For certain problems, though, the quest for tighter relaxations— indeed, the quest for any better approximation algorithms—has ended. Results using probabilistically checkable proofs (PCPs) show that for a variety of problems such as max-3sat, set cover, max-2sat, etc., known approximation guarantees cannot be improved if P ≠ NP. Thus PCP-based techniques provide an explanation for our inability to provide tighter relaxations for these problems.

However, for many other problems, including all four problems mentioned in the opening paragraph, the PCP-based results are fairly weak or nonexistent and fall well below the integrality gaps of the best relaxations. The best hardness result for vertex cover—due to Dinur and Safra [11], who improved upon a long line of work—only shows that 1.36-approximation is NP-hard. The best hardness result for metric tsp only shows that 1.01-approximation is NP-hard [25], yet decades of work has failed to yield a relaxation with integrality gap better than 1.5 [32] (or 4/3, if one believes a well-known conjecture [17]). For graph expansion and related graph problems essentially no hardness results exist yet we only know relaxations with integrality gap Ω(logn) (Shmoys [29]).

When decades of work has failed to turn up tighter relaxations, one should seriously investigate the possibility that no tighter relaxations exist. However, proving such a statement may be related to P vs. NP, since linear programming is complete for P.^{1} Thus it seems necessary to work with subfamilies of linear relaxations. An integrality gap result for a large subfamily of relaxations may then be viewed as a lower bound for a restricted computational model, analogous say to lower bounds for monotone circuits [27] and for proof systems [5]. An example is Yannakakis’s result [33] that representing tsp (the exact version) using a symmetric linear program requires exponentially many constraints—this ruled out some approaches to P = NPthat were being tried at the time.

In this paper we prove nonexistence of tighter relaxations for vertex cover among three fairly general families of LPs. For all families we prove an integrality gap of 2 − o(1). An interesting aspect of our result—also the reason for the paper’s title—is that no explicit description is known for the LPs in the three families. However, we can show that they use inequalities that have a fairly local view of the graph. This lets us construct graphs in which any minimum vertex cover must contain almost all the vertices (in particular, it must contain (1 − α)n vertices where α > 0 is very small), yet the all-1/2 solution (or something close to it) is feasible for each inequality. Since the complement of a vertex cover is an independent set, and vice versa, our results may also be trivially rephrased to say that the integrality gap of the independent set problem for our three families of LPs is unbounded, even though the graphs witnessing these gaps have independent sets of size Ω(n).

Proving Integrality Gaps without Knowing the Linear Program

In the first two families of relaxations we allow only the variables x_{1},x_{2},...,x_{n}∈ [0,1] for the vertices and no auxiliary variables. Some such restriction seems necessary because auxiliary variables would give the LP the power of arbitrary polynomial-time computations. The third family allows auxiliary variables implicitly, but in a very controlled way—namely, as part of the “lift-and-project” procedure of Lovász and Schrijver [24].

1Erratum: The conference version of this paper erroneously stated that proving such a statement is tantamount to proving P ≠ NP. However, it is actually an open problem [33] whether P = NP implies that the vertex cover polytope has a polynomial size description (where additional variables are allowed).

Theory of Computing, Volume 2 (2006), pp. 19–52 20

The first family consists of linear programs that can include arbitrary inequalities on any set of ϵn variables, for some small constant ϵ > 0.

The second family consists of linear programs containing inequalities with low defect. Usually one defines “defect” for facets of the independent set polytope (see for instance [24, 23]); here we will make an analogous definition for the vertex cover polytope (i.e., the convex hull of all integra vertex covers): The defect of a vertex cover polytope facet a^{T}x ≥ b, where a is a vector of integers and b an integer, is defined to be 2b − ∑_{i}a_{i}. The defects of such facets are always non-negative [24]. Linear programs in the second family are allowed those inequalities defining facets of the vertex cover polytope with defect at most ϵn. An integrality gap of 2 − o(1) for this family is a simple corollary of the one for the first family.

The third family consists of linear programs obtained from O(logn) rounds of a “lift-and-project” construction of Lovász and Schrijver [24]. This is a method that underlies semidefinite relaxations used in many recent approximation algorithms starting with Goemans and Williamson [19]. The LS procedure over many rounds generates tighter and tighter linear relaxations for 0/1 optimization problems. It is more round-efficient than classical cutting planes procedures such as Gomory-Chvátal [8] since it generates every valid inequality in at most n rounds. Even in one round it generates nontrivial inequalities for vertex cover. Furthermore, the set of inequalities derivable in O(1) rounds—this could be an exponentially large set—has a polynomial-time separation oracle, thus allowing the Ellipsoid method to optimize over this set. In general, one can optimize over the set of inequalities obtained after r rounds in n^{O(r)} time. We show that at least Ω(logn) rounds of the LS procedure (the LP version, not the semidefinite version) are necessary to reduce the integrality gap below 2 − o(1).^{2} Note that characterizing the set of inequalities obtained in even O(1) rounds has proved difficult; even the case of 2 rounds is open.

For the first family, better integrality gaps can be obtained for independent set than those trivially implied by our results for vertex cover. We show that for linear programs where each inequality uses at most n^{ϵ(1−γ)} variables (here ϵ,γ > 0 are any small constants), the integrality gap for independent set is n^{1−ϵ} . This is essentially tight since constraints using n^{ϵ} variables can clearly approximate independent set within a factor of n^{1−ϵ} .

Our techniques seem applicable to problems other than vertex cover (and independent set) and have been the subject of future work [6, 1, 30]. These developments are discussed in the related work section below. However, several open problems remain. For example, extending our ideas to semidefinite relaxations as well as to the semidefinite programming analogue of the Lovász-Schrijver procedure remains a difficult and interesting open problem. We discuss this and other open problems further in Section 5.

We also note that the integrality gaps proven in Section 2 are strong enough (namely, they apply to LPs that we do not know how to solve in 2^{o(n)} time) that they may be seen as complementary to PCP-based results. Even if it were shown using PCPs that (2 − ϵ)-approximation to vertex cover is NP-hard, the proof would probably involve even more complex reductions than those in [11]. Thus it might reduce 3sat formulae of size n to vertex cover on graphs of size n^{c}, where c is astronomical. Even if we assume 3sat has no 2^{o(n)} time algorithms, such a reduction would not rule out an integrality gap of 1.1 (say) for the relaxations in Section 2. In other words, even in a world with PCP-based results, our methods may be useful for ruling out subexponential approximation algorithms that use linear programming approaches.

2Erratum: The conference version of this paper [3] argued Ω(\sqrt{logn}) rounds of the LS procedure were needed to reduce the integrality gap for vertex cover below 2−o(1). However, Cheriyan and Qian [7] observed that the argument in [3] was incomplete. In the current paper we give a new (complete) proof of the LS round lower bound. Independently, Qian [26] also provides a fix for the proof in [3]. However, our new proof has the advantage of showing that in fact at least Ω(logn) rounds of LS tightenings are needed to reduce the integrality gap below 2 − o(1).

Theory of Computing, Volume 2 (2006), pp. 19–52 21

Related work A few authors have viewed the Lovász-Schrijver procedure as a proof system and shown that Ω(n) rounds are required to derive certain simple inequalities (e.g., Goemans and Tunçel [18], Cook and Dash [9]). However, these papers do not consider the issue of how the integrality gap improves (or fails to improve) after a few rounds of the LS procedure. A recent (and independent) paper by Feige and Krauthgamer [16] considers the question of integrality gaps, but for the maximum clique problem on a random graph with edge probabilities 1/2. They show that Ω(logn) rounds of LS_{+} , the semi-definite version of Lovász and Schrijver’s lift-and-project procedure, are necessary and sufficient to reduce the integrality gap to 1 (with high probability over the choice of the graph). However, this result does not directly give any lower bound on the approximability of vertex cover, since in their graphs both the minimum (integral) vertex cover and the optimal value of the relaxations considered are about n.

Subsequently to our work there have appeared several papers proving integrality gaps for relaxations using both the LP and SDP versions of the Lovász-Schrijver lift-and-project method. Buresh-Oppenheim et al. [6] show that Ω(n) rounds of LS_{+} are needed to obtain relaxations for max-ksat, k ≥ 5, with integrality gaps less than (2^{k}− 1)/2^{k}− ϵ. Alekhnovich et al. [1], building upon [6], show that Ω(n) rounds of LS_{+} are needed to obtain relaxations for max-3sat with integrality gaps less than 7/8−ϵ. In addition they showed that Ω(n) rounds of LS_{+} are needed to obtain relaxations for set-cover and rankk hypergraph vertex cover with integrality gaps less than (1−ϵ)lnn and k−1−ϵ, respectively. Note that PCP-based results (such as those of Håstad [20], Feige [15] and Dinur et al. [10]) already ruled out non-trivial polynomial-time approximation algorithms for these problems (assuming P ≠ NP). However, they did not rule out slightly subexponential approximation algorithms (defined as those running in 2^{n^{c}} time for c < 1) for the reasons mentioned earlier, namely, the blowup in instance size caused by the PCP-based reductions.

Tourlakis [30], building on techniques used in the current paper, proved that Ω(loglogn) rounds of LS are needed to obtain relaxations for rank-k hypergraph vertex cover with integrality gaps less than k − ϵ.

2 The first family

In this section we prove integrality gaps for linear programs in {x_{1},x_{2},...,x_{n}}for both vertex cover and independent set where the programs allow any constraint of the form a^{T}x ≤ b such that the coefficient vector a is nonzero for at most ϵn coordinates. In other words, each constraint involves at most ϵn variables. Such linear programs may have exponential size and may not have a polynomialtime separation oracle. In fact, there are linear programs in this family for which finding such an oracle would imply P = NP. We only require that all 0/1 vertex covers and 0/1 independent sets in the graph are feasible for the vertex cover and independent set relaxations, respectively.

The natural candidate graph for exhibiting integrality gaps for these relaxations would be one where the largest independent set has size at most αn for some small α > 0, but every induced subgraph on ϵn vertices has an independent set of size nearly ϵn/2. However, it turns out that the local property we need for our graph is somewhat stronger: all small induced subgraphs have small fractional chromatic number which we define below.

We will construct the required graph by the probabilistic method in Theorem 2.3. This result appears to be new, although it fits in a line of results starting with Erdős [13] showing that the chromatic number of a graph cannot be deduced from “local considerations” (see also Alon and Spencer [2], p.130).

Definition 2.1. A fractional γ-coloring of a graph G is a multiset 𝒞 = {U_{1},...,U_{N}} of independent sets of vertices (for some N) such that every vertex is in at least N/γ members of 𝒞. The fractional chromatic number of G is

χ_{f} (G) = inf{γ : G has a fractional γ-coloring} .

Note that if G has a k-coloring with color classes U_{1},...,U_{k} then 𝒞 = {U_{1},...,U_{k}} is also a fractional k-coloring of G. Consequently, χ_{f} (G) ≤ χ(G).

Remark 2.2. If χ_{f} (G) = γ and {U_{1},...,U_{N}}is a fractional γ-coloring for G, we will usually assume without loss of generality that each vertex of G (by deleting it from a few of the U_{i} if necessary) is in exactly N/γ sets.

Note that strictly speaking, having χ_{f} (G) = γ does not guarantee that there exists a fractional γcoloring for G; it only guarantees a fractional (γ +ϵ)-coloring for all ϵ > 0. Nevertheless, in the interest of keeping our notation clean, we will always assume that a fractional γ-coloring does exist (in particular, we will only consider rational γ). This slight inaccuracy will not affect the validity of our arguments.

Theorem 2.3. Let 0 < α,δ < 1/2 be constants. Then there exist constants β = β(α,δ) > 0 and n_{0} = n_{0}(α,β,δ) such that for every n ≥ n_{0} there is a graph with n vertices and independence number at most αn such that every subgraph induced by a subset of at most βn vertices has fractional chromatic number at most 2 + δ.

Let H be the graph constructed in Theorem 2.3 with α,δ arbitrarily close to 0 and let β be as given by the theorem.

Theorem 2.4. The vector with all coordinates \frac{1+δ}{2+δ} is feasible for any linear relaxation for H in which each constraint involves at most βn variables. Consequently, since any independent set is the complement of a vertex cover, and vice versa, the integrality gap is at least (1 − α) · \frac{2+δ}{1+δ} .

Proof. It suffices to show that the all-\frac{1+δ}{2+δ} vector is feasible for any set of constraints A_{I} · x ≤ b_{I} where I ⊆ {1,...,n}has size at most βn.

So fix any subset I of at most βn vertices and let {U_{1},...,U_{N}}be a fractional (2 + δ)-coloring for I such that each vertex in I is in exactly a 1/(2 + δ) fraction of the U_{i}’s (see Remark 2.2). Note that each I \ U_{i} is a vertex cover in the subgraph induced by I and hence can be extended to a vertex cover of the entire graph. By definition, the characteristic vector of any such vertex cover extension obeys A_{I}·x ≤ b_{I}. So since these constraints only involve variables from I, it follows that any vector in ℝ^{n} that has 1_{I\U_{i}} (the characteristic vector of I \ U_{i}) in the coordinates corresponding to I is also feasible for A_{I} · x ≤ b_{I}.

Consider the vectors v_{1},v_{2},...,v_{N} ∈ ℝ^{n} where v_{i} is equal to 1_{I\U_{i}} in those coordinates corresponding to I and is (1 + δ)/(2 + δ) otherwise. Each such vector satisfies A_{I} · x ≤ b_{I}, so convexity implies that the same is also true for the average vector \frac{1}{N}(v_{1}+ v_{2}+ ··· + v_{N}). Since each vertex in I lies in exactly a 1 − 1/(2 + δ) = (1 + δ)/(2 + δ) fraction of the vertex covers, this average is the all-\frac{1+δ}{2+δ} vector. Thus this vector satisfies A_{I} · x ≤ b_{I}, as desired.

Note that the same construction can also be used to prove integrality gaps for linear relaxations for independent set:

Corllary 2.5. Every independent set linear relaxation for H (where H is the same graph as above) where each constraint in the relaxation has at most βn variables has integrality gap at least \frac{1}{α(2+δ)} .

Proof. Let I be any subset of at most βn vertices and let {U_{1},...,U_{N}} be a fractional (2 + δ)-coloring for I such that each vertex in I is in exactly a 1/(2+δ) fraction of the U_{i}’s (see Remark 2.2). Now define vectors v_{1},v_{2},...,v_{N} ∈ ℝ^{n} as follows: Let v_{i} equal 1_{U_{i}} in those coordinates corresponding to I but have v_{i} equal 1/(2 + δ) outside I. Then each v_{i} is feasible for all constraints involving variables only from I. But then, the average of the v_{i}’s, i.e., the vector with all coordinates 1/(2 + δ), is also feasible for these constraints.

Denote the size of the maximum independent set in a graph G by α(G). The above argument in fact yields the following more general theorem.

Theorem 2.6. Let G be a graph on n vertices such that every subgraph induced by a set of at most β(n) vertices has fractional chromatic number ≤ C. Then the vector with all coordinates \frac{1}{C} is feasible for any linear relaxation of the independent set constraints for G in which each relaxed constraint involves at most β(n) variables. Consequently, the integrality gap for the relaxation is at least \frac{n}{α(G)C}.

This suggests we can obtain larger integrality gaps for independent set if we further limit the number of variables in each constraint. In Section 2.2 below we show that this is indeed the case by exhibiting graphs for which Theorem 2.6 yields the following:

Theorem 2.7. Fix ϵ,γ > 0. Then there exists a constant n_{0} = n_{0}(ϵ,γ) such that for every n ≥ n_{0} there exists a graph G with n vertices for which the integrality gap of any linear relaxation for independent set in which each constraint uses at most n^{ϵ(1−γ)} variables is at least n^{1−ϵ} .

2.1 Proof of Theorem 2.3

The proof uses standard random graph theory supplemented with a couple of new ideas. Let us recall the standard part (see [2]). If we pick a random graph G using the familiar 𝒢(n,p) model and choose p appropriately, then the largest independent set in G has size at most αn and yet the induced subgraph on every subset of βn vertices has an independent set of size close to βn/2. By deleting a few edges—too few to disturb anything else—we can assume that G has no small cycles (i.e., has high girth). Finally, we will show that these induced subgraphs on βn vertices also satisfy a sparsity condition; this latter property appears to be previously unknown.

We then show in Lemma 2.13 that every high girth graph satisfying this sparsity condition has fractional chromatic number 2 + δ on every induced subgraph with at most βn vertices. The proof uses induction on the subgraph size. The main idea in the inductive step is to exhibit a long path inside every subgraph using Lemma 2.12. Peeling away the path gives a smaller subgraph that is colored (fractionally) using the inductive assumption. Lemma 2.11 is then used to extend this fractional coloring, completing the induction.

Now we give details. The next lemma concerns the “standard random graph theory” mentioned above, together with the new sparsity condition.

Lemma 2.8. Given real numbers α,η with 0 < α < 1/250 and 0 < η < 1/2, let λ > e^{2} and β > 0 be such that

2\frac{logλ}{λ} ≤ α  (2.1)

and

β < (eλ)^{−2/η} .  (2.2)

Let g ≥ 3 be an integer such that g ≤ logn/(3logλ). Then there is an integer n_{0} = n_{0}(λ,η,g) such that for every n ≥ n_{0} there is a graph H of order n, girth at least g and independence number at most αn such that every subgraph of H with ℓ ≤ βn vertices contains at most (1 + η)ℓ edges.

Remark 2.9. Condition (2.1) is satisfied if we take

λ = (3/α)log(1/α) .

Proof of Lemma 2.8. Let us consider the space of random graphs 𝒢(n,p) with p = λ/n. We will show that a graph G_{n,p} drawn randomly from this space, modulo a few small alterations, satisfies with high probability the three properties required of H in the statement of the lemma.

Let 0 < α_{0} < α be such that

1 + log(1/α_{0}) < λα_{0}/2 .  (2.3)

Inequality (2.1) implies that we can choose such an α_{0}. In order to avoid unnecessary clutter, in what follows, we shall drop the integrality signs (in particular, we shall write α_{0}n instead of ⌈α_{0}n⌉); this slight inaccuracy will not endanger the validity of the arguments. Also, as usual, we shall assume that n is large enough to make our inequalities hold.

1. The probability that for some ℓ, 4 ≤ ℓ ≤ 1/η, some ℓ-set in G_{n,p} spans at least ℓ + 1 edges is at most

∑_{ℓ=4}^{1/η} \binom{n}{ℓ} \binom{\binom{ℓ}{2}}{ℓ + 1} ( \frac{λ}{n}) ^{ℓ+1} ≤ ∑_{ℓ=4}^{1/η} ( \frac{en}{ℓ})^{ℓ}( \frac{e\frac{ℓ(ℓ+1)}{2}}{ℓ + 1} ) ^{ℓ+1} ( \frac{λ}{n}) ^{ℓ+1}

= \frac{1}{en} ∑_{ℓ=4}^{1/η} ℓ( \frac{e^{2}λ}{2} ) ^{ℓ+1}

= O(n^{−1} ) .

Similarly, the probability that for some ℓ, 1/η < ℓ < βn, some ℓ-set spans at least (1 + η)ℓ edges is at most

∑_{ℓ=1/η}^{βn} \binom{n}{ℓ} \binom{\binom{ℓ}{2}}{(1 + η)ℓ} ( \frac{λ}{n}) ^{(1+η)ℓ} ≤ ∑_{ℓ=1/η}^{βn} [( \frac{en}{ℓ}) ( \frac{eℓ}{2(1 + η)} ) ^{1+η} ( \frac{λ}{n}) ^{1+η} ]^{ℓ}

≤ ∑_{ℓ=1/η}^{βn} [e^{2}(ℓ/n)^{η}λ^{1+η} ]^{ℓ} .  (2.4)

We bound (2.4) by first splitting the sum into two quantities and bounding each of them: Letting C = e^{2}λ^{1+η} we have that,

∑_{ℓ=1/η}^{\sqrt{n}} [e^{2}(ℓ/n)^{η}λ^{1+η} ]^{ℓ} ≤ ∑_{ℓ=1/η}^{\sqrt{n}} ( \frac{C}{\sqrt{n}}) ^{ℓ} = ( \frac{C}{\sqrt{n}}) ^{1/η+1} \frac{1 − (C/\sqrt{n})^{\sqrt{n}−1/η}}{1 − (C/\sqrt{n})} = O(n^{−1} ) .

On the other hand, (2.2) implies that D = e^{2}β^{η}λ^{2} < 1, and hence,

∑_{ℓ=\sqrt{n}+1}^{βn} [e^{2}(ℓ/n)^{η}λ^{1+η} ]^{ℓ} ≤ ∑_{ℓ=\sqrt{n}}^{βn} D^{ℓ} ≤ \frac{D^{\sqrt{n}+1}}{1 − D} = O(n^{−1} ) .

So, (2.4) is at most O(n^{−1} ).

Hence, the probability that all ℓ-sets, ℓ ≤ βn, in G_{n,p} span at most (1 + η)ℓ edges is at least 1 − O(n^{−1} ).

2. Let I = I(G_{n,p}) be the number of independent sets of ⌈α_{0}n⌉ vertices in G_{n,p}. Note that

𝔼(I) = \binom{n}{α_{0}n} ( 1 − \frac{λ}{n}) ^{\binom{α_{0}n}{2}} ≤ ( ( \frac{e}{α_{0}} ) e^{−λα_{0}/2} ) ^{α_{0}n} = γ_{0}^{α_{0}n} .

Inequality (2.3)implies that γ_{0} < 1, so the probability that G_{n,p} contains an independent set of α_{0}n vertices is exponentially small.

3. Call a cycle in G_{n,p} short if its length is less than g. The expected number of short cycles is less than

∑_{ℓ=3}^{g−1} \frac{n^{ℓ}}{ℓ} ( \frac{λ}{n}) ^{ℓ} = ∑_{ℓ=3}^{g−1} \frac{λ^{ℓ}}{ℓ} ≤ n^{1/3} .

By Markov’s inequality, G_{n,p} has at most n^{1/2} short cycles with probability at least 1 − O(n^{−1/6} ). Deleting an edge from each of these cycles then gives a graph of girth at least g.

Consequently, with probability 1 − O(n^{−1/6} ), G_{n,p} has no set of ℓ ≤ βn vertices spanning more than (1+η)ℓ edges, and moreover, if we delete an edge from each short cycle then the independence number of the new graph H = G′_{n,p} is at most

α_{0}n + \sqrt{n}< αn .

This graph H has the required properties.

Now we establish some basic properties of χ_{f}. It is easy to check that a path with at least one edge has fractional chromatic number 2. In particular, a graph has fractional chromatic number less than 2 if and only if it is an independent set. The proof of the next lemma is left to the reader.

Lemma 2.10. 1. If C_{k} denotes the cycle of length k then χ_{f} (C_{2ℓ}) = 2 and χ_{f} (C_{2ℓ+1}) = (2ℓ + 1)/ℓ.

2. If |V (G_{1}) ∩ V (G_{2})| ≤ 1 then χ_{f} (G_{1}∪ G_{2}) = max{χ_{f} (G_{1}), χ_{f} (G_{2})}.

The next Lemma concerns the fractional chromatic number of a graph that contains a long path (i.e., the vertices on the path’s interior have no edges outside the path edges).

Lemma 2.11. Let ℓ ≥ 2 and let G be a graph obtained by adding a path x_{0}x_{1}...x_{ℓ+1} to a graph G′, where x_{0},x_{ℓ+1} ∈ V (G′) and x_{i} ∉ V (G′) for 1 ≤ i ≤ ℓ. Then χ_{f} (G) ≤ max\{χ_{f} (G′), \frac{2ℓ}{ℓ−1} \}.

Proof. Let χ_{f} (G′) = 1/γ and suppose first that γ > 1/2. Then G is an independent set and the lemma follows since paths have fractional chromatic number 2.

So assume γ ≤ 1/2. By Remark 2.2 we can assume without loss of generality that there exists a multiset 𝒞′= {U′_{1},...,U′_{N}} of independent sets in G′ such that every vertex of G′ is in exactly γN of these sets. So since x_{0} ∈ G′and γ ≤ 1/2, there exists a multiset 𝒜 containing exactly N/2 sets from 𝒞′ such that no set in 𝒜 contains x_{0}. Similarly, there exists a multiset ℬ of N/2 sets taken from 𝒞′such that no set in ℬ contains x_{ℓ+1}.

Fix i, 1 ≤ i ≤ n. We will define a colouring 𝒞_{i} for G \ {x_{i}} (i.e., G with x_{i} removed) by extending the sets U′_{h}in 𝒞′to independent sets U_{h} in G \ {x_{i}}. Moreover, our colouring will have the property that each x_{j}, 1 ≤ j ≤ ℓ, j ≠ i will be in exactly half the sets of 𝒞_{i}. Our approach will be as follows: Fix a set U′_{h}∈ 𝒞′. If U′_{h}∈ 𝒜 we will then add to U_{h} every other node in the path fragment from x_{1} to x_{i−1} starting with x_{1}: That is, x_{1},x_{3},x_{5},... will be in U_{h}, but x_{2},x_{4},... will not. If instead U′_{h} ∉ 𝒜 then x_{2},x_{4},x_{6},... will be in U_{h}, but x_{1},x_{3},... will not. Similarly, we will decide which of the nodes x_{i+1} ,x_{i+2} ,...,x_{ℓ} to add to U_{h} depending on whether or not U′_{h}is in ℬ. Since 𝒜 and ℬ each contain exactly half the sets of 𝒞′, it will follow that each x_{j}, 1 ≤ j ≤ ℓ, j ≠ i, is in exactly half the sets of 𝒞_{i}.

Formally, the exact construction is as follows: Fix U′_{h}∈ 𝒞′. For 1 ≤ j ≤ i, if U′_{h}∈ 𝒜 then add x_{j} to U_{h} if j is odd; if instead U′_{h} ∉ 𝒜 then add x_{j} to U_{h} if j is even. For i ≤ j ≤ ℓ, if U′_{h}∈ ℬ then add x_{j} to U_{h} if ℓ − j is even; if instead U′_{h} ∉ ℬ then add x_{j} to U_{h} if ℓ − j is odd.

Let 𝒞 = ∪𝒞_{i}. This multiset of ℓN sets is then a fractional colouring for G. Note that every vertex of G′is in γℓN sets of 𝒞. Moreover, every x_{i}, 1 ≤ i ≤ ℓ, is in \frac{1}{2}(ℓ − 1)N sets. Consequently, every vertex of G is in at least a min\{γ, \frac{ℓ−1}{2ℓ} \} fraction of the sets of 𝒞. Hence, χ_{f} (G) ≤ max\{\frac{1}{γ}, \frac{2ℓ}{ℓ−1} \}.

For real k > 1 call a graph k-sparse if it has no subgraph with ℓ vertices and more than kℓ edges. Hence, sparsity quantifies (half of) the maximum average degree of subgraphs. This concept is closely related to that of degeneracy: Recall that a graph is k-degenerate if every subgraph has a vertex of degree at most k. Hence, if k is a natural number and ϵ > 0, then a (\frac{k+1}{2} − ϵ)-sparse graph is k-degenerate; conversely, every k-degenerate graph is k-sparse.

Recall that a graph is k-connected if there does not exist a set of k − 1 vertices whose removal disconnects the graph. By length of a path we will mean the number of edges.

Lemma 2.12. Let ℓ ≥ 1 be an integer and 0 < η < \frac{1}{3ℓ−1} , and let G be a 2-connected (1 + η)-sparse graph which is not a cycle. Then G contains a path of length at least ℓ + 1 whose internal vertices have degree 2 in G.

Proof. Suppose that G has n vertices and does not contain a path of length ℓ + 1 with ℓ internal vertices of degree 2 in G. Since G is a 2-connected graph with more edges than vertices, G consists of a certain k ≥ 2 number of branch-vertices (i.e., vertices of degree at least 3) and the induced paths joining them, say P_{1},...,P_{m}, where m ≥ ⌈3k/2⌉, and all internal nodes in these paths have degree 2. Let ℓ_{i} ≤ ℓ denote the length of P_{i}. Then,

n = k + ∑_{i=1}^{m} (ℓ_{i}− 1) = k − m + e(G) ≤ k − m + (1 + η)n ,

and so, m − k ≤ ηn. On the other hand,

n = k + ∑_{i=1}^{m} (ℓ_{i}− 1) ≤ k + m(ℓ − 1) ,

and hence m − k ≤ η(k + m(ℓ − 1)). But then, since m ≥ ⌈3k/2⌉, it follows that η ≥ 1/(3ℓ − 1), a contradiction.

Lemma 2.13. Let h ≥ 2 be an integer and 0 < η < \frac{1}{3h+2} . Then every (1 + η)-sparse graph G of girth at least 2h has χ_{f} (G) ≤ 2 + \frac{2}{h}.

Proof. We use induction on the number of vertices. The base case is trivial. Assume the statement is true when the number of vertices is at most m and G is a graph with m+1 vertices. If it is not 2-connected, it has a vertex v whose removal disconnects the graph and hence we can complete the inductive step using part 2 of Lemma 2.10. So assume G is 2-connected. If it is a cycle then its length must be at least 2h, and hence χ_{f} is at most 2+ \frac{1}{h} by part 1 of Lemma 2.10. So assume G is not a cycle. But then, by Lemma 2.12, G contains a path of length h+2 whose internal vertices have degree 2 in G. Let G′be the graph obtained from G by deleting these internal vertices (together with the edges incident with them). By the induction hypothesis, χ_{f} (G′) ≤ 2+ \frac{2}{h}, and so by Lemma 2.11 we have χ_{f} (G) = max\{χ_{f} (G′),2+ \frac{2}{h}\} ≤ 2+ \frac{2}{h}. This completes the induction and the Lemma is proved.

We can now prove Theorem 2.3.

Proof of Theorem 2.3. Set h = ⌈2/δ⌉, g = 2h and η = \frac{1}{3h+3} . Choose λ > e^{2} and β > 0 to satisfy inequalities (2.1) and (2.2). Let H be a graph of order n whose existence is guaranteed by Lemma 2.8. Thus, H has independence number at most αn, and if G is a subgraph of H with at most βn vertices then G is (1 + η)-sparse and has girth at least g = 2h. Hence, by Lemma 2.13, χ_{f} (G) ≤ 2 + \frac{2}{h} ≤ 2 + δ, completing the proof.

2.2 Proof of Theorem 2.7

Throughout this section, log will denote base-2 logarithms.

By Theorem 2.6, to obtain a large integrality gap we need to construct graphs where the independence and local fractional chromatic numbers are as small as possible. One way to do this is using graph products.

Definition 2.14. The inclusive graph product G×H of two graphs G and H is the graph on V (G×H) = V (G) × V (H) where {(x,y),(x′,y′)} ∈ E(G × H) iff (x,x′) ∈ E(G) or (y,y′) ∈ E(H). The notation G^{k} indicates the graph resulting by taking the k-fold inclusive graph product of G with itself.

The key observation is that α(G × H) = α(G) × α(H) and χ_{f} (G × H) = χ_{f} (G)χ_{f} (H) (the former fact is easy; for the latter see [14] for a proof). Moreover, if all sets of size at most βn have fractional chromatic number C in G, then all sets of size at most βn in G^{k} have fractional chromatic number C^{k}. So taking products of a graph with itself drives down the relative sizes of both the independence and local fractional chromatic numbers. However, since the resulting graph is much larger, the fractional chromatic number is small only for negligibly sized subgraphs. To get around this we instead consider an appropriately chosen (small) random subgraph of G^{k}. The particular construction we use is due to Feige [14]. By choosing each vertex of G^{k} independently at random with probability α(G)^{−k} and analyzing the resulting induced subgraph, Feige proves the following theorem (we sketch a proof below for completeness; see [14] for details):

Theorem 2.15 (Feige [14]). There exists an integer n_{0} such that for every graph G on n ≥ n_{0} vertices and any integer k, there exists a graph G_{k} such that:

1. G_{k} is a vertex induced subgraph of G^{k}.

2. \frac{1}{2}( \frac{n}{α(G)})^{k} ≤ |V (G_{k})| ≤ 2( \frac{n}{α(G)})^{k} .

3. α(G_{k}) ≤ \frac{kα(G)lnn}{ln(kα(G)lnn)} .

Proof. (Sketch) Select each vertex of G^{k} independently and at random with probability α(G)^{−k}. Let Ĝ be the induced subgraph of G^{k} obtained by this process. We show that Ĝ satisfies the above three properties with high probability.

By construction, Ĝis an induced subgraph of G^{k}. Moreover, the probability that |V (Ĝ)| deviates by more than a factor of 2 from its expectation is negligible. For the last property, fix a maximal independent set I in G^{k}. The expected number of vertices from I in Ĝ is at most 1. Chernoff bounds sharply bound the probability that more than \frac{kα(G)lnn}{ln(kα(G)lnn)} vertices of I survive in Ĝ. The last property can now be seen to hold with high probability by observing that G contains at most n^{α(G)} maximal independent sets and by observing that all maximal independent sets in G^{k} are the direct product of k maximal independent sets in G. In particular, the probability that more than \frac{kα(G)lnn}{ln(kα(G)lnn)} vertices of any maximal independent set of G^{k} survive in Ĝcan be shown to go to 0 as n grows.

Our strategy for proving Theorem 2.7 will then be as follows: We will start with a graph G where both the independence number and local fractional chromatic number are already small (such a graph will exist by Theorem 2.3) and then apply Feige’s randomized graph product to it.

Now the details. Fix arbitrarily small constants α,δ > 0 and n > 0 such that n ≥ n_{0} where n_{0} is from Theorem 2.15. Provided that n is chosen sufficiently large, Theorem 2.3 implies that there exists a graph G on n vertices such that α(G) ≤ αn and such that for some constant β > 0, all induced subgraphs of G with at most βn vertices have chromatic number ≤ 2 + δ.

Fix an arbitrarily small constant d > 0 and let G_{k} be the graph given by Theorem 2.15 for k = d logn. Let N = |V (G_{k})|. Note that N = Θ(α^{−k}) = Θ(n^{d log(1/α)}). On the other hand, all subsets of G_{k} of size at most

βn = Θ( N^{\frac{1/d}{log(1/α)}} )  (2.5)

have fractional chromatic number ≤ (2 + δ)^{k}.

By Theorem 2.6 it follows that any linear relaxation of the independent set constraints for G_{k} where the relaxed constraints contain at most βn variables has integrality gap (the Θ̃ notation indicates asymptotic order up to logarithmic factors):

Θ( \frac{α^{−k}}{(2 + δ)^{k} \frac{kαnlnn}{ln(kαnlnn)}} ) = Θ̃( n^{d(log(1/α)−log(2+δ))−1} ) = Θ̃( N^{1− \frac{1/d+log(2+δ)}{log(1/α)}} ) .  (2.6)

Since we can take α and δ to be arbitrarily small in Theorem 2.3 (provided n is large enough), and since d > 0 can also be chosen arbitrarily small, it follows that we can simultaneously make (2.5) more than N^{ϵ(1−γ)} and (2.6) more than N^{1−ϵ} . The theorem follows.

3 The second family

For an n-vertex graph G, let VC(G) denote the convex hull of all integral vertex covers for G, i.e., the convex hull of all 0/1 vectors x ∈ ℝ^{n} satisfying x_{i}+x_{j} ≥ 1 for all edges {i,j} in G. All non-trivial facets of the polytope VC(G) can be expressed in the form a^{T}x ≥ b where a ∈ ℤ_{+}^{V} and b ∈ ℤ_{+} . (By non-trivial we exclude facets of the form x_{i} ≥ 0 and x_{i} ≤ 1, and require that at least two coordinates of a are nonzero.) Note moreover that the non-trivial facets of any relaxation for VC(G) lying in [0,1]^{n} must also be of the form a^{T}x ≥ b where a ∈ ℤ_{+}^{V} and b ∈ ℤ_{+} .

While VC(G) requires exponentially many non-trivial facets to completely specify, it may be that a smaller subset of these facets yields a linear relaxation with integrality gap less than 2 − ϵ for some ϵ > 0. In this section we consider relaxations defined by those facets of VC(G) having low defect.

The defect of a facet a^{T}x ≥ b of VC(G) is defined to be 2b − ∑_{i}a_{i}. It follows from the proof of an analogous result for the Independent Set polytope by Lovász and Schrijver [24] that this quantity is always non-negative for facets of VC(G). For more about defects of facets see [24] and also Lipták and Lovász [23].

We now generalize the results of Section 2 to any linear relaxation for vertex cover defined by facets of VC(G) with defect at most ϵn:

Theorem 3.1. For all γ > 0 there exists a constant ϵ > 0 such that the integrality gap is at least 2 − γ for any relaxation for vertex cover consisting of inequalities of the form a^{T}x ≥ b (a ∈ Z_{+}^{n},b ∈ Z_{+} ) and defect at most ϵn.

Proof. Let α,δ > 0 be constants such that (1 − α)\frac{2+δ}{1+δ} ≥ 2 − γ, and let H be the graph constructed in Theorem 2.3 for these constants. Let the defect of our relaxation be at most ϵn where ϵ = βδ/(2 + δ). The theorem will follow by showing that the vector x_{δ} with all coordinates (1 + δ)/(2 + δ) is feasible.

There are two types of facets a^{T}x ≥ b. If ∑_{i}a_{i} ≤ βn then the constraint only involves βn variables and so the feasibility of the vector x_{δ} follows as in Theorem 2.4. If ∑_{i}a_{i} > βn then the feasibility of x_{δ} follows by direct substitution:

∑_{i} a_{i} \frac{1 + δ}{2 + δ} = ∑_{i} a_{i} \frac{δ}{2(2 + δ)} + \frac{1}{2} ∑_{i} a_{i} > \frac{βnδ}{2(2 + δ)} + \frac{1}{2} ∑_{i} a_{i} = \frac{ϵn}{2}+ \frac{1}{2} ∑_{i} a_{i} ≥ b .

4 The third family

Consider the standard relaxation for vertex cover:

x_{i}+ x_{j} ≥ 1  ∀{i,j} ∈ E  (Edge constraint)  (4.1)

In this relaxation the x_{i}’s are real numbers in [0,1]. Suppose we wish to tighten the relaxation to force the x_{i}’s to be 0/1 in any optimal solution. To this end, we could introduce any constraints satisfied by 0/1 vertex covers. For instance, the x_{i}’s can be required to satisfy for every odd-cycle C,

∑_{i∈C}x_{i} ≥ \frac{|C|+ 1}{2}  (Odd-cycle constraint)  (4.2)

Many other families of inequalities satisfied by 0/1 vertex covers are known, but a complete listing will probably never be found because of complexity reasons.

Lovász and Schrijver [24] give an automatic method for generating over many rounds all valid inequalities. More generally, they give a method for obtaining tighter and tighter relaxations for any 0/1 optimization problem starting from an arbitrary relaxation. The idea is to “lift” to n^{2} dimensions and then project back to n-space. This is why the procedure is called “lift-and-project” or “lifting.” The motivation is to try to simulate the power of quadratic programs. Solving quadratic programs is of course NP-hard since adding the constraints x_{i}(1 − x_{i}) = 0 to a linear relaxation forces 0/1 answers. For example, all 0/1 vertex covers satisfy

x_{i}^{2}= x_{i}  (4.3)
(1 − x_{i})(1 − x_{j}) = 0  ∀{i,j} ∈ E .  (4.4)

To linearly simulate these constraints, we can introduce new linear variables Y_{ij} to “represent” the products x_{i}x_{j} and then demand that the “lifted” variables satisfy x_{i} = Y_{ii} and 1−x_{i}−x_{j} +Y_{ij} = 0 for all edges {i,j}. We can then take positive linear combinations of these constraints to eliminate all “quadratic” terms and obtain constraints using only the original variables x_{i}.

Formally, given a relaxation

a_{r}^{T}x ≥ b  r = 1,2,...,m  (4.5)
0 ≤ x_{i} ≤ 1  i = 1,2,...,n ,  (4.6)

one round of LS produces a system of inequalities in (n + 1)^{2} variables Y_{ij} for i,j = 0,1,...,n. As already mentioned, the intended “meaning” is that Y_{ij} = x_{i}x_{j} and Y_{00} = 1,Y_{0i} = x_{i}x_{0} = x_{i}, and Y_{00} = 1 so every quadratic expression in the x_{i}’s can be viewed as a linear expression in the Y_{ij}’s. This is how the quadratic inequalities below should be interpreted. The following inequalities are derived in one round:

(1 − x_{i})a_{r}^{T}x ≥ (1 − x_{i})b  ∀i = 1,...,n, ∀r = 1,...,m
x_{i}a_{r}^{T}x≥ x_{i}b  ∀i = 1,...,n, ∀r = 1,...,m
x_{i}x_{i}= x_{i}  ∀i = 1,2,...,n

The last constraint corresponds to the fact that x_{i}^{2} = x_{i} for 0/1 variables. Since any positive combination of the above inequalities is also implied, we can use such combinations to eliminate all non-linear terms.

Lovász and Schrijver show that every inequality valid for the integral hull is generated in at most n rounds. Moreover, they show that the set of inequalities derivable in one round for the vertex cover relaxation are exactly the odd-cycle inequalities. To illustrate, we now show how to derive in one round the odd-cycle inequality x_{1} + x_{2} + x_{3} ≥ 2 for a triangle on nodes {1,2,3} starting from the edge constraints (4.1). One round of LS generates the following inequalities (amongst others):

(1 − x_{1})(x_{1}+ x_{2}) ≥ 1 − x_{1}  (4.7)
(1 − x_{2})(x_{2}+ x_{3}) ≥ 1 − x_{2}  (4.8)
(1 − x_{3})(x_{1}+ x_{3}) ≥ 1 − x_{3}  (4.9)
x_{1}(x_{2}+ x_{3}) ≥ x_{1}  (4.10)
x_{2}(x_{1}+ x_{3}) ≥ x_{2}  (4.11)

Adding inequality (4.7) twice to the sum of the remaining four inequalities and then simplifying using the rule x_{i}^{2} = x_{i} gives x_{1}+ x_{2}+ x_{3} ≥ 2 as desired.

No exact characterization exists for the inequalities derivable in subsequent rounds. However, we do know that the set of inequalities derivable in O(1) rounds has a polynomial-time separation oracle. For more details see [24].

To understand our results, the reader only needs to know the next Lemma taken from [24] and which gives an alternate characterization of LS liftings useful for proving lower bounds. The notation uses homogenized inequalities. Let FR(G) be the cone in ℝ^{n+1} that contains a vector (x_{0},x_{1},...,x_{n}) iff it satisfies 0 ≤ x_{i} ≤ x_{0} for all i as well as the edge constraints x_{i} + x_{j} ≥ x_{0} for each edge {i,j} ∈ G. All cones below will be in ℝ^{n+1} and we are interested in the slice cut out by the hyperplane x_{0} = 1. Denote by N^{r}(FR(G)) the feasible cone of all inequalities obtained from r rounds of the LS lifting procedure. Let e_{i} denote the ith unit vector so that Ye_{i} denotes the ith column of Y. The next lemma defines the effect of one round.

Lemma 4.1 ([24]). If K is a cone in ℝ^{n+1} , then x ∈ N^{m}(K) iff there is an (n + 1) × (n + 1) symmetric matrix Y satisfying

1. Ye_{0} = diag(Y) = x.

2. For 1 ≤ i ≤ n, both Ye_{i} and Y (e_{0}− e_{i}) are in N^{m−1}(K).

Following [6] we will call the matrix Y witnessing that x ∈ N^{m}(K) in the above lemma a protection matrix since it “protects” x for one round of LS tightening.

In practice, we will only be concerned with showing that vectors x ∈ ℝ^{n+1} with x_{0} = 1 survive a round of lifting. For such points, we have the following corollary of Lemma 4.1:

Corllary 4.2. Let K be a cone in ℝ^{n+1} and suppose x ∈ ℝ^{n+1} where x_{0} = 1. Then x ∈ N^{m}(K) iff there is an (n + 1) × (n + 1) symmetric matrix Y satisfying

1. Ye_{0} = diag(Y) = x.

2. For 1 ≤ i ≤ n: If x_{i} = 0 then Ye_{i} = 0; If x_{i} = 1 then Ye_{i} = x; Otherwise, Ye_{i}/x_{i}, Y (e_{0}− e_{i})/(1 − x_{i}) both lie in the projection of N^{m−1}(K) onto the hyperplane x_{0} = 1.

Our main theorem for this section is the following:

Theorem 4.3. For all ϵ > 0 there exists an integer n_{0} and a constant δ(ϵ) > 0 such that for all n ≥ n_{0}, there exists an n vertex graph G for which the integrality gap of N^{r}(FR(G)) for any r ≤ δ(ϵ)logn is at least 2 − ϵ.

The proof of Theorem 4.3 relies on the following two theorems. The first (which also follows as a subcase from the arguments used to prove Lemma 2.8) is essentially due to Erdős [12]; see Bollobás [4], Theorem 4, Ch VII. The second, Theorem 4.5, will be proved in Section 4.2 with an overview of the argument first given in Section 4.1.

Theorem 4.4. For any α > 0 there is an n_{0}(α) such that for every n ≥ n_{0}(α) there are graphs on n vertices with girth at least logn/(3log(1/α)) but no independent set of size greater than αn.

Let y_{γ} denote the vector (1, \frac{1}{2} + γ, \frac{1}{2} + γ,..., \frac{1}{2} + γ) where 0 < γ < \frac{1}{2}.

Theorem 4.5. Let G = (V,E) have girth(G) ≥ 16r/γ. Then y_{γ} ∈ N^{r}(FR(G)).

Proof of Theorem 4.3. Let γ = ϵ/8 and α = ϵ/4, and let n_{0} be the constant from Theorem 4.4 for this α. For n ≥ n_{0}, let G be the n-vertex graph given by Theorem 4.4. Finally, let δ(ϵ) = \frac{ϵ}{384log(4/ϵ)}. Then by Theorem 4.5, y_{γ} is in N^{r}(FR(G)) for all r ≤ δ(ϵ)logn, and hence, the integrality gaps for all these polytopes is at least 2(1 − α)/(1 + 2γ) ≥ 2 − ϵ.

4.1 Intuition for Theorem 4.5

Lemma 4.1 (and Corollary 4.2) suggest using induction to prove Theorem 4.5. We first will identify for each j some large set of vectors within each polytope N^{j}(FR(G)) called the “palette” for N^{j}(FR(G)). In stage j of the induction we will show the following: For each vector x in the palette for N^{j}(FR(G)), there exists a protection matrix Y such that for all i ∈ [n] the vectors Ye_{i} and Y (e_{0} − e_{i}) all lie in the palette for the previous polytope N^{j−1} (FR(G)) (Figure 1). The condition that such a protection matrix exists can be expressed as an LP. Hence, to show that a protection matrix exists for each x in the palette for N^{j}(FR(G)) we show using Farkas’s lemma that the LP is feasible. The theorem then follows since our definition for the palette for N^{r}(FR(G)) will ensure that it contains y_{γ}.

S. Arora, B. Bollobás, L. Lovász, I. Tourlakis

Figure 1: Chain of dependencies in the proof of Theorem 4.5: Each palette is contained in its respective polytope because some other palette is contained in the previous polytope.

Theory of Computing, Volume 2 (2006), pp. 19–52 34

Since our protection matrices will be found using LP duality, we will pick the simplest palettes possible in order to ensure that our LPs are also as simple as possible (and hence easy to analyze). To understand what desirable properties the palette vectors should have, let us look at the simpler problem of showing that y_{γ} ∈ N(FR(G)) (rather than showing y_{γ} ∈ N^{r}(FR(G))) and make some observations about the constraints the conditions in Corollary 4.2 force upon a protection matrix for y_{γ}.

To that end, consider the projected “columns” Ye_{i}/y_{γ}^{(i)} and Y (e_{0} − e_{i})/(1 − y_{γ}^{(i)}) of Y (from condition 2 of Corollary 4.2). These vectors must satisfy the edge constraints. As will be shown in Section 4.4 (see equation (4.14)), the constraints forcing this are given by the following constraint:

α_{i} ≤ Y_{ij} + Y_{ik} ≤ α_{i}+ (α_{j} + α_{k}− 1)  ∀i ∈ {1,...,n},∀{j,k} ∈ E .  (4.12)

Fix i. If j_{1} is adjacent to i, then (4.12) implies \frac{1}{2} + γ ≤ Y_{ii}+ Y_{ij_{1}} ≤ \frac{1}{2} + 3γ. Since Y is a protection matrix for y_{γ}, it must satisfy Y_{ii} = y_{γ}^{(i)} = \frac{1}{2} + γ. Hence, 0 ≤ Y_{ij_{1}} ≤ 2γ. Now consider a node j_{2} at distance 2 from j_{1}. Then (4.12), together with the fact that 0 ≤ Y_{ij_{1}} ≤ 2γ for all j_{1} adjacent to i, imply that \frac{1}{2} − γ ≤ Y_{ik} ≤ \frac{1}{2} + 3γ. In turn, for a node j_{3} at distance 3 from i we must have 0 ≤ Y_{ij_{3}} ≤ 4γ; and for a node j_{4} at distance 4 from i we have \frac{1}{2} − 3γ ≤ Y_{ij_{4}} ≤ \frac{1}{2} + 3γ. So as j gets further and further from i, the constraints on Y_{ij} implied by (4.12) get looser and looser so that for nodes j sufficiently far from i (distance 2/γ more than suffices) no constraint on Y_{ij} is implied. So intuitively, for such j we should be able to choose Y_{ij} such that node j remains \frac{1}{2} + γ in both Ye_{i}/y_{γ}^{(i)} and Y (e_{0} − e_{i})/(1 − y_{γ}^{(i)}). Note that the fact that the coordinates of y_{γ} are \frac{1}{2} + γ instead of \frac{1}{2} is crucial in ensuring that the effects of the edge constraints die out as we get further away from node i. Note also that we have implicitly assumed that our graph has girth larger than 2/γ so that two nodes cannot be connected by two paths of different lengths both less than 2/γ—intuitively this is why Theorem 4.5 requires large girth. We should also mention that we have simplified things by ignoring constraints required by Corollary 4.2 forcing the projected “columns” to lie in [0,1]^{n+1} : these tighten the above constraints on the Y_{ij} a bit but the intuition given above is mostly unchanged.

In any case, the above suggests that to prove y_{γ} ∈ N(FR(G)) we could use a palette consisting of all vectors in FR(G) which are \frac{1}{2} + γ everywhere except perhaps on some ball of radius 2/γ in G. As such, we can add “palette constraints” to the LP defining Y forcing all nodes j distant from i to be \frac{1}{2} + γ in both Ye_{i}/y_{γ}^{(i)} and Y (e_{0}−e_{i})/(1−y_{γ}^{(i)}). In fact, since Y must also be symmetric, the actual constraints we will add will force the following: for all pairs of nodes i,j with distance at least 2/γ between them, the jth nodes in Ye_{i}/y_{γ}^{(i)} and Y (e_{0}− e_{i})/(1 − y_{γ}^{(i)}), and the ith nodes Ye_{j}/y_{γ}^{(j)} and Y (e_{0}− e_{j})/(1 − y_{γ}^{(j)}) must all be \frac{1}{2} + γ.

The proof of Theorem 4.5 will use generalized versions of the above palette: The palettes for each polytope N^{j}(FR(G)) will consist of vectors from FR(G) that are \frac{1}{2} + γ except in a few neighbourhoods (see Definition 4.6 in Section 4.2 for the precise statement). For a vector x in the palette for N^{j}(FR(G)) the LP used to find a protection matrix Y for x will have two types of constraints: constraints that force Y to satisfy the conditions in Corollary 4.2 and constraints that force the “columns” Ye_{i}/x_{i} and Y (e_{0}− e_{i})/(1 − x_{i}) to belong to the “palette” for N^{j−1} (FR(G)).

The palettes we will use will have the following property: The diameter of the largest neighbourhood H in G such that H consists entirely of nodes with values not equal to \frac{1}{2} + γ will grow linearly with the number of rounds. Hence, our method is limited to proving integrality gaps for at most O(logn) rounds since only graphs with girth O(logn) yield large integrality gaps.^{3}

4.2 Proof of Theorem 4.5

The theorem will be proved by induction where the inductive hypothesis requires a set of vectors other than just y_{γ} to be in N^{m}(FR(G)) for m ≤ r (the “palettes” from Section 4.1). These vectors will be essentially all-(\frac{1}{2} +γ), except possibly for a few small neighborhoods where the vector can take arbitrary nonnegative values so long as the edge constraints are satisfied. Let Ball(w,R) denote the set of vertices within distance R of w in G.

Definition 4.6. Let S ⊆ {1,...,n}, R be a positive integer and γ > 0. Then a nonnegative vector (α_{0},α_{1},...,α_{n}) ∈ [0,1]^{n+1} with α_{0} = 1 is an (S,R,γ)-vector if the entries satisfy the edge constraints and if for each w ∈ S there exists a positive integer R_{w} such that

1. ∑_{w∈S}(R_{w}+ \frac{2}{γ}) ≤ R

2. For distinct w,w′∈ S, Ball(w,R_{w}) ∩ Ball(w′,R_{w′}) = ∅

3. α_{j} = \frac{1}{2} + γ for each j ∉ ∪_{w∈S}Ball(w,R_{w})

We will say that the integers {R_{w}}_{w∈S} witness that α is an (S,R,γ)-vector.

Let R^{(r)} = 0 and let R^{(m)}= R^{(m+1)} + \frac{4}{γ} for 0 ≤ m < r. Note that 4R^{(m)}≤ girth(G) for 0 ≤ m ≤ r. To prove Theorem 4.5 we will prove the inductive claim below. Since the set of (∅,R^{(r)},γ)-vectors consists precisely of the vector y_{γ}, the theorem will then follow as a subcase of the case m = r. Inductive Claim for N^{m}(FR(G)): For every set S of at most r − m vertices, every (S,R^{(m)},γ)-vector is in N^{m}(FR(G)). Base case m = 0. Trivial since (S,R^{(0)},γ)-vectors satisfy the edge constraints for G. Proof for m + 1 assuming truth for m. Let α be an (S,R^{(m+1)},γ)-vector where |S| ≤ r − m − 1. To show that α ∈ N^{m}(FR(G)) it suffices to find a protection matrix Y for α satisfying the properties of Corollary 4.2. We exploit the structure of (S,R,γ)-vectors and prove some important structural properties of these vectors in Lemma 4.7, which then enables us to argue that such a protection matrix exists thereby completing the induction step.

Note first that α is trivially an (S ∪ i,R^{(m)},γ)-vector for any i ∈ G. Lemma 4.7, which we now state and prove in Section 4.3 below, says that for appropriate sets S′, |S′| ≤ r − m, α is also an (S′,R^{(m)},γ)- vector enjoying crucial additional structural properties.

Lemma 4.7. Let i be such that α_{i} ∉ {0,1}. Then there exists a set S_{i} ⊆ {1,...n}, |S_{i}| ≤ r − m, and positive integers {R_{w}^{(m)}}_{w∈S_{i}} such that,

1. α is an (S′,R^{(m)},γ)-vector with witnesses {R_{w}^{(m)}}_{w∈S_{i}}

2. i ∈ ∪_{w∈S_{i}}Ball(w,R_{w}^{(m)})

3In the conference version of this paper [3], the palettes were picked such that the diameter of the largest neighbourhood grew quadratically in the number of rounds, thereby yielding integrality gaps only for O(\sqrt{logn}) rounds.

Theory of Computing, Volume 2 (2006), pp. 19–52 36

3. For each ℓ ∉ ∪_{w∈S_{i}}Ball(w,R_{w}^{(m)}), any path between i and ℓ in G contains at least \frac{2}{γ} consecutive vertices ℓ such that α_{ℓ} = \frac{1}{2} + γ

By the induction hypothesis, for any S′⊆ {1,...,n}such that |S′| ≤ r − m, every (S′,R^{(m)},γ)-vector is in N^{m}(FR(G)). Hence, to show that α ∈ N^{m+1}(FR(G)) it suffices by Corollary 4.2 to exhibit an (n + 1) × (n + 1) symmetric protection matrix Y that satisfies:

A. Ye_{0} = diag(Y) = α,

B. For each i such that α_{i} = 0, we have Ye_{i} = 0; for each i such that α_{1} = 1, we have Ye_{0} = Ye_{i}; otherwise, Ye_{i}/α_{i} and Y (e_{0}−e_{i})/(1−α_{i}) are (S_{i},R^{(m)},γ)-vectors, where S_{i} as well as the integers {R_{w}^{(m)}}_{w∈S_{i}} witnessing that these vectors are (S_{i},R^{(m)},γ)-vectors are given by Lemma 4.7 for i.

We will complete the proof of the induction step (and hence of Theorem 4.5) by showing in Section 4.4 below that a matrix Y exists satisfying conditions A and B.

4.3 Proof of Lemma 4.7

Let {R_{w}^{(m+1)}}_{w∈S} witness that α is an (S,R^{(m+1)},γ)-vector and let C = ∪_{w∈S}Ball(w,R_{w}^{(m+1)}). There are two cases depending on whether Ball(i, \frac{2}{γ}) intersects C or not.

In the first (easy) case, Ball(i, \frac{2}{γ}) does not intersect C. Then let S_{i} = S ∪ \{i\}, let R_{i}^{(m)} = \frac{2}{γ}, and let

R_{w}^{(m)}= R_{w}^{(m+1)} for w ∈ S. It is easy to see that the conditions of the lemma are satisfied by these choices. So consider the second case where Ball(i, \frac{2}{γ}) does intersects C. Let

T_{1} = \{ w ∈ S: i ∈ Ball ( w,R_{w}^{(m+1)} + \frac{2}{γ}) \} .

That is, T_{1} consists of all points in S whose balls, slightly enlarged, contain i. Note that it may be that i ∈ S, in which case i ∈ T_{1}.

Now let

D = ⋃_{w∈T_{1}}Ball ( w,R_{w}^{(m+1)} + \frac{2}{γ}) .

Since ∑_{w∈S}(R_{w}^{(m+1)} + \frac{2}{γ}) ≤ R^{(m+1)} < \frac{1}{2} girth(G) − \frac{2}{γ}, it follows that D is a tree. Let q be a longest path in D and let w_{1} be a node in the middle of this path. Then certainly,

D ⊆ Ball ( w_{1}, ∑_{w∈T_{1}}( R_{w}^{(m+1)} + \frac{2}{γ}) ) .

We will now increase the size of this “big ball” around w_{1} (perhaps also moving its centre in the process) until there are no points w ∈ S outside the “big ball” for which Ball(w,R_{w}^{(m+1)} + \frac{2}{γ}) intersects the “big ball”. We do this as follows:

Suppose Ball(w_{1},∑_{w∈T_{1}}(R_{w}^{(m+1)} + \frac{2}{γ})) intersects Ball(w′,R_{w′}^{(m+1)} + \frac{2}{γ}) for some w′∈ S\T_{1}. Add w′to T_{1} and call the new set T_{2}. Reasoning as before, there exists w_{2} ∈ G such that,

⋃_{w∈T_{2}}Ball ( w,R_{w}^{(m+1)} + \frac{2}{γ}) ⊆ Ball ( w_{2}, ∑_{w∈T_{2}}( R_{w}^{(m+1)} + \frac{2}{γ}) ) .

In general, at stage j if Ball(w_{j},∑_{w∈T_{j}}(R_{w}^{(m+1)} + \frac{2}{γ})) intersects Ball(w′,R_{w′}^{(m+1)} + \frac{2}{γ}) for some w′∈ S\T_{j}, then add w′to T_{j}, call the new set T_{j+1} , and find a new w_{j+1} ∈ G (using again the same arguments as before) such that,

⋃_{w∈T_{j+1}} Ball ( w,R_{w}^{(m+1)} + \frac{2}{γ}) ⊆ Ball ( w_{j+1} , ∑_{w∈T_{j+1}} ( R_{w}^{(m+1)} + \frac{2}{γ}) ) .

Continue in this way until the first stage k for which no point w′in S\T_{k} such that Ball(w′,R_{w′}^{(m+1)} + \frac{2}{γ})

intersects Ball(w_{k},∑_{w∈T_{k}}(R_{w}^{(m+1)} + \frac{2}{γ})). Let T = T_{k} and u = w_{k}.

We can now define S_{i} and {R_{w}^{(m)}}_{w∈S_{i}}: Let S_{i} = (S\T) ∪ {u}. For w ∈ S\T, let R_{w}^{(m)}= R_{w}^{(m+1)}; let

R_{u}^{(m)}= \frac{2}{γ} + ∑_{w∈T}( R_{w}^{(m+1)} + \frac{2}{γ}) .

To complete the proof of the lemma we need to show that α is an (S_{i},R^{(m)},γ)-vector witnessed by these {R_{w}^{(m)}} and that the remaining two conditions in the statement of the lemma are satisfied.

Note first that

∑_{w∈S_{i}}( R_{w}^{(m)}+ \frac{2}{γ}) = ∑_{w∈S\T}( R_{w}^{(m)}+ \frac{2}{γ}) + ( R_{u}^{(m)}+ \frac{2}{γ})

= ∑_{w∈S\T}( R_{w}^{(m+1)} + \frac{2}{γ}) + ( ∑_{w∈T}( R_{w}^{(m+1)} + \frac{2}{γ}) + \frac{4}{γ})

= ∑_{w∈S}( R_{w}^{(m+1)} + \frac{2}{γ}) + \frac{4}{γ} ≤ R^{(m+1)} + \frac{4}{γ} = R^{(m)} .

The inequality above follows from the fact that α is an (S,R^{(m+1)},γ)-vector witnessed by the integers R_{w}^{(m+1)}. Hence α satisfies condition (1) of being an (S_{i},R^{(m)},γ)-vector witnessed by the integers {R_{w}^{(m)}}.

Next note that by construction, Ball(u,R_{u}^{(m)}) does not intersect ∪_{w∈S\T}Ball(w,R_{w}^{(m)}). Moreover, since α is an (S,R^{(m+1)},γ)-vector witnessed by the integers R_{w}^{(m+1)}, it follows that

Ball(w,R_{w}^{(m)}) ∩ Ball(w′,R_{w′}^{(m)}) = ∅

for distinct w,w′∈ S\T. Also, by construction, α_{j} = \frac{1}{2} + γ for all j ∉ ∪_{w∈S_{i}}Ball(w,R_{w}^{(m)}). Hence α satisfies conditions (2) and (3) of being an (S_{i},R^{(m)},γ)-vector witnessed by the integers {R_{w}^{(m)}}.

Next note that by construction, we have on one hand that

⋃_{w∈T}Ball ( w,R_{w}^{(m+1)} + \frac{2}{γ}) ⊆ Ball ( u,R_{u}^{(m)}− \frac{2}{γ}) .

On the other hand, Ball(u,R_{u}^{(m)}) does not intersect ∪_{w∈S\T}Ball(w,R_{w}^{(m+1)}). Since α is an (S,R^{(m+1)},γ)- vector witnessed by the integers R_{w}^{(m+1)}, it thus follows from the definition of such vectors that for all vertices k in Ball(u,R_{u}^{(m)})\Ball(u,R_{u}^{(m)}− \frac{2}{γ}), we have α_{k} = \frac{1}{2} + γ. Hence condition (3) of the lemma holds.

Finally, condition (2) of the lemma holds since by construction i ∈ ⋃_{w∈T} Ball(w,R_{w}^{(m+1)} + \frac{2}{γ}). The lemma follows.

4.4 Existence of Y

We will show that Y exists by representing conditions A and B as a linear program and then showing that the program is feasible. This approach was first used in [24] and subsequently in the conference version of this paper.

Our notation will assume symmetry, namely, Y_{ij} will represent Y_{{i,j}}. Condition A requires that:

Y_{kk}= α_{k}, ∀k ∈ {1,...,n} .  (4.13)

Condition B requires that the vectors Ye_{i}/α_{i} and Y (e_{0}−e_{i})/(1−α_{i}) are (S_{i},R^{(m)},γ)-vectors. In particular, we need constraints on the variables Y_{ij} forcing these vectors to satisfy both the edge constraints as well as the extra structural properties enjoyed by (S_{i},R^{(m)},γ)-vectors.

The following constraints imply that Ye_{i}/α_{i} and Y (e_{0}−e_{i})/(1−α_{i}) satisfy the edge constraints: For all i ∈ {1,...,n} and all {j,k} ∈ E:

α_{i} ≤ Y_{ij} + Y_{ik} ≤ α_{i}+ (α_{j} + α_{k}− 1) ,  (4.14)

To see that the above inequalities force Ye_{i}/α_{i} and Y (e_{0} − e_{i})/(1 − α_{i}) to satisfy the edge constraints note first that Ye_{i}/α_{i} satisfies the edge constraint for some edge {j,k} iff the jth and kth coordinates of Ye_{i}/α_{i} sum to at least 1. In equations, this requires Y_{ij}/α_{i}+ Y_{ik}/α_{i} ≥ 1, or equivalently α_{i} ≤ Y_{ij} + Y_{ik} for the edge {j,k}. Similarly, the equation Y_{ij} + Y_{ik} ≤ α_{i} + (α_{j} + α_{k}− 1) implies that Y (e_{0} − e_{i})/(1 − α_{i}) satisfies the edge constraint for edge {j,k}.

Let (i,t) be a pair of vertices such that α_{i},α_{t} ∉ {0,1}. Let S_{i} ⊆ {1,...,n}be the set, and {R_{w}^{(m)}}_{w∈S_{i}} the witnesses given by Lemma 4.7 for i. Then i,t are called a distant pair if t ∉ ∪_{w∈S_{i}}Ball(w,R_{w}^{(m)}). (Note then that α_{t} = \frac{1}{2} + γ.) To ensure that Ye_{i}/α_{i} and Y (e_{0}− e_{i})/(1 − α_{i}) are (S_{i},R^{(m)},γ)-vectors witnessed by {R_{w}^{(m)}}_{w∈S_{i}} (as required by condition B) it suffices to ensure that the tth coordinates of Ye_{i}/α_{i} and Y (e_{0}− e_{i})/(1 − α_{i}) are \frac{1}{2} + γ for all distant pairs (i,t). In particular, for all such pairs,

Y_{it} = α_{i}α_{t} = α_{i}(\frac{1}{2} + γ) .  (4.15)

Remark 4.8. By Lemma 4.7, distant pairs have the property that every path in G that connects them contains at least 2/γ consecutive vertices k such that α_{k} = \frac{1}{2} + γ. In particular, any such path contains 2/γ − 1 consecutive edges whose endpoints are “oversatisfied” by α by 2γ.

Finally, (S_{i},R^{(m)},γ)-vectors must lie in [0,1]^{n+1} . The following constraints imply that Ye_{i}/α_{i} and Y (e_{0}− e_{i})/(1 − α_{i}) are in [0,1]^{n+1} :

0 ≤ Y_{ij} ≤ α_{i},  ∀i,j ∈ {1,...,n},i ≠ j  (4.16)
−Y_{ij} ≤ 1 − α_{i}− α_{j},  ∀i,j ∈ {1,...,n},i ≠ j  (4.17)

Constraints (4.13)–(4.17) suffice to force Y to satisfy conditions A and B. We will not directly analyze these constraints but instead analyze the following four constraint families which imply constraints (4.13)–(4.17) but are also in a cleaner form:

Y_{ij}≤ β(i,j),  ∀i,j ∈ {1,...,n}  (4.18)
−Y_{ij} ≤ δ(i,j),  ∀i,j ∈ {1,...,n}  (4.19)
Y_{ij} + Y_{ik}≤ a(i,j,k),  ∀{j,k} ∈ E  (4.20)
−Y_{ij} − Y_{ik}≤ b(i,j,k),  ∀{j,k} ∈ E  (4.21)

Here (1) β(i,j) = α_{i}α_{j} if i,j is a distant pair and β(i,j) = min(α_{i},α_{j}) otherwise; (2) δ(i,j) = −α_{i} if i = j, δ(i,j) = −α_{i}α_{j} if i,j is a distant pair, and δ(i,j) = 1 − α_{i} − α_{j} otherwise; (3) a(i,j,k) = α_{i}+ (α_{j} + α_{k}− 1); and (4) b(i,j,k) = −α_{i}. Note that since α ∈ [0,1]^{n+1} , β(i,j) + δ(i,j) ≥ 0.

To prove the consistency of constraints (4.18)–(4.21), a special combinatorial version of Farkas’s lemma will be used similar to that used in [24] and the conference version of this paper [3]. Before giving the exact combinatorial form we require some definitions.

Let H = (W,F) be the graph where W = {Y_{ij} : i,j ∈ {1,...,n}} (i.e., there is a vertex for each variable Y_{i,j}) and the edges F consist of all pairs {Y_{ij},Y_{ik}} such that {j,k} ∈ E. Vertices in W labelled Y_{ii} are called diagonal. Given an edge {Y_{ij},Y_{ik}} in H, call i its bracing node and {j,k} ∈ E its bracing edge. An edge \{i,j\} in G is called overloaded if α_{i} = α_{j} = \frac{1}{2} + γ. An edge \{Y_{ij},Y_{ik}\} in H is overloaded if its bracing edge is overloaded.

Let p be a walk v_{0},v_{1},...,v_{r} on H and let e_{1},...,e_{r} be the edges in H traversed by this walk. An alternating sign assignment (P,N) for p assigns either all the odd or all the even indexed edges of p to the set P with the remaining edges assigned to N. Given an alternating sign assignment (P,N) for p, an endpoint of p is called positive (negative, respectively) if it is incident to an edge in P (N, respectively). We will be particularly concerned with the positive diagonal endpoints of a walk.

Given a path p in H with an alternating sign assignment (P,N), let

S_{1}^{(p;P,N)}= ∑_{{Y_{ij},Y_{ik}}∈P}a(i,j,k) + ∑_{{Y_{ij},Y_{ik}}∈N}b(i,j,k) .  (4.22)

Suppose the endpoints of p are labelled by Y_{ij},Y_{kℓ}. Define S_{2}^{(p;P,N)}to be D + E where D is δ(i,j) if Y_{ij} is a positive endpoint and is β(i,j) otherwise; and E is δ(k,ℓ) if Y_{kℓ}is a positive endpoint and is β(k,ℓ) otherwise. Let S^{(p;P,N)}= S_{1}^{(p;P,N)}+ S_{2}^{(p;P,N)}.

\begin{aligned}−Y_{12} & ≤ −α_{1}α_{2} \\ Y_{12}+ Y_{13} & ≤ α_{1}+ (α_{2}+ α_{3}− 1) \\ −Y_{13}− Y_{34} & ≤ −α_{3} \\ Y_{34}+ Y_{35} & ≤ α_{3}+ (α_{4}+ α_{5}− 1) \\ −Y_{35}− Y_{56} & ≤ −α_{5} \\ Y_{56} & ≤ α_{5}α_{6} \\ −Y_{77} & ≤ −α_{7} \\ Y_{77}+ Y_{78} & ≤ α_{7}+ (α_{7}+ α_{8}− 1) \\ −Y_{78} & ≤ 1 − α_{7}− α_{8} \end{aligned}

Figure 2: A positive integer linear combination of the constraints where the LHS is 0, and which corresponds to two walks p_{1} and p_{2} in H with alternating sign assignments (P_{1},N_{1}) and (P_{2},N_{2}), respectively.

Lemma 4.9 (Special case of Farkas’s Lemma). The constraints on the variables Y_{ij} are unsatisfiable iff there exists a walk p on H and an alternating sign assignment (P,N) for p such that S^{(p;P,N)}is negative.

Proof. Note first that by Farkas’s lemma, constraints (4.18)–(4.21) are unsatisfiable iff there exists a positive rational linear combination of them where the LHS is 0 and the RHS is negative.

Now suppose that there exists a path p in H and an alternating sign assignment (P,N) such that S^{(p;P,N)}< 0. Consider the following linear integer combination of the constraints: (1) For each edge {Y_{ij},Y_{ik}} ∈ p, if {Y_{ij},Y_{ik}} ∈ P, add the constraint Y_{ij} + Y_{ik} ≤ a(i,j,k); if {Y_{ij},Y_{ik}} ∈ N, add the constraint −Y_{ij} − Y_{ik} ≤ b(i,j,k); (2) For each endpoint Y_{ij} of p, if it is a negative endpoint add the constraint Y_{ij} ≤ β(i,j); if it is a positive endpoint add the constraint −Y_{ij} ≤ δ(i,j). But then, for this combination of constraints the LHS equals 0 while the RHS equals S^{(p;P,N)}< 0. So by Farkas’s lemma the constraints are unsatisfiable.

Now assume on the other hand that the constraints are unsatisfiable. So there exists a positive rational linear combination of the constraints such that the LHS is 0 and the RHS is negative. In fact, by clearing out denominators, we can assume without loss of generality that this linear combination has integer coefficients. Hence, as β(i,j) + δ(i,j) ≥ 0 for all i,j, our combination must contain, without loss of generality, constraints of type (4.20) and (4.21). Moreover, since the LHS is 0, for each Y_{ij} appearing in the integer combination there must be a corresponding occurrence of −Y_{ij}. But then, it is easy to see that the constraints in the integer linear combination can be grouped into a set of paths {p_{i}} in H each with its own alternating sign assignment such that the RHS of the linear combination equals ∑ S^{(p_{i};P_{i},N_{i})} (for an example, see Figure 2). But then, since the RHS is negative, it must be that at least one of the paths p in the set is such that S^{(p;P,N)}< 0. The lemma follows.

So to show that the constraints for the matrix Y are consistent, we will show that S^{(p;P,N)}≥ 0 for any walk p on H and any alternating sign assignment (P,N) for p.

To that end, fix a walk p on H and an alternating sign assignment (P,N) for p. To simplify notation we drop the superscript (p;P,N) from S_{1}^{(p;P,N)}, S_{2}^{(p;P,N)}and S^{(p;P,N)}. Let v_{0},v_{1},...,v_{r} be the nodes visited by p in H (a node may be visited multiple times) and let e_{1},...,e_{r} be the edges in H traversed by p. We divide our analysis into three cases depending on whether none, one or both endpoints of p are positive diagonal. We will show that in any of these cases S ≥ 0.

We first note three easy facts about p used below:

Proposition 4.10. Let C be the subgraph of G induced by the bracing edges for e_{1},...,e_{n}. Then,

1. Subgraph C consists of at most two connected components;

2. If p visits a diagonal node, then C is connected; Moreover, if v_{0} is diagonal and v_{r} = Y_{st}, then C contains a path in G from s to t;

3. If p visits at least two diagonal nodes then C contain a cycle.

Proof. We sketch a proof of the first fact; the other two are similar.

Consider the edges e_{1},...,e_{r} in order. As long as the bracing node in successive edges does not change, then the bracing edges of these successive edges form a path p′ in G. If the bracing node changes, say at edge e_{i} in p, the bracing edge for e_{i} now starts a new path p′′in G. Moreover the last vertex w in G visited by p′is the bracing node for e_{i}. The bracing edges of the edges following e_{i} in p now extend p′′in G until an edge e_{j} is encountered with a new bracing node. But then, the bracing edge for e_{j} must contain w. Hence, the bracing edge for e_{j} now extends path p′in G. Continuing this argument we see that each time the bracing node changes we go back and forth from having the bracing edges contributing to the paths p′and p′′in G. Fact (1) follows (also see Figure 3).

Case 1: No endpoint of p is positive diagonal

Suppose the endpoints v_{0},v_{r} of p are labelled by Y_{ab} and Y_{cd}, respectively, and consider the following sum S′_{2}: If v_{0} is a negative endpoint, then it contributes α_{a}α_{b} to S′_{2}; otherwise it contributes −α_{a}α_{b}. Similarly, if v_{r} is negative, then it contributes α_{c}α_{d} to S′_{2} and otherwise it contributes −α_{c}α_{d}. Since α ∈ [0,1]^{n+1} and neither endpoint is positive diagonal, it follows that S_{2} ≥ S′_{2}. So to prove that S ≥ 0 in this case, it suffices to show S_{1}+ S′_{2} ≥ 0.

To that end, consider the following sum:

∑_{{Y_{ij},Y_{ik}}∈P}(−α_{i}α_{j} − α_{i}α_{k}) + ∑_{{Y_{ij},Y_{ik}}∈N}(α_{i}α_{j} + α_{i}α_{k}) .  (4.23)

By definition of an alternating sign assignment it follows that (4.23) telescopes and equals S′_{2}. Hence,

S ≥ S_{1}+ S′_{2} = ∑_{{Y_{ij},Y_{ik}}∈P}(a(i,j,k) − (α_{i}α_{j} + α_{i}α_{k})) + ∑_{{Y_{ij},Y_{ik}}∈N}(b(i,j,k) + (α_{i}α_{j} + α_{i}α_{k}))  (4.24)
= ∑_{{Y_{ij},Y_{ik}}∈P}(1 − α_{i})(α_{j} + α_{k}− 1) + ∑_{{Y_{ij},Y_{ik}}∈N}α_{i}(α_{j} + α_{k}− 1) .  (4.25)

Proving Integrality Gaps without Knowing the Linear Program

Figure 3: A walk p in H and the corresponding pair of walks p′,p′′in G formed by the bracing edges in p. The walks p′,p′′could meet, e.g., if p visits a diagonal vertex in H.

Theory of Computing, Volume 2 (2006), pp. 19–52 43

Now the bracing edges for all edges in P and N are in G. Moreover, α satisfies the vertex cover edge constraints (4.1) for G. Hence, α_{j} + α_{k} ≥ 1 for all edges {Y_{ij},Y_{ik}} ∈ P ∪ N. But then, since we always have 0 ≤ α_{i} ≤ 1, it follows that all summands in (4.25) are at least 0 and hence, S ≥ 0 as desired.

Case 2: One endpoint of p is positive diagonal

Assume without loss of generality that v_{0} is the positive endpoint and is labelled Y_{11}, and suppose the other endpoint v_{r} is labelled Y_{st}. There are two subcases:

Subcase 1: {s,t} is a distant pair: By Proposition 4.10, if C is the subgraph of G induced by the bracing edges for e_{1},...,e_{n}, then there is a path p′in C (and hence in G) from s to t. So since s,t are distant, Remark 4.8 implies that p′contains at least 2/γ − 1 consecutive overloaded edges.

We first define some notation to refer to the summands appearing in (4.25) which will also be important in this subcase: For an edge e = {Y_{ij},Y_{ik}}in our path p,

ζ(e) = \{ \begin{matrix}(1 − α_{i})(α_{j} + α_{k}− 1), & if \{Y_{ij},Y_{ik}\}∈ P \\ α_{i}(α_{j} + α_{k}− 1), & if \{Y_{ij},Y_{ik}\}∈ N \end{matrix}

As noted in Case 1, ζ(e) ≥ 0 for all e ∈ p.

In Case 1 we showed that S ≥ 0 by first defining a sum S′_{2} such that S_{2} ≥ S′_{2} and then noting that S_{1}+S′_{2} = ∑_{e∈p} ζ(e). Unfortunately, in the current subcase, since p contains a positive diagonal endpoint, it is no longer true that S_{2} ≥ S′_{2}. However, it is easy to see that S_{2} ≥ S′_{2} − (α_{1} − α_{1}^{2}). In particular, S ≥ ∑_{e∈p} ζ(e) − (α_{1} − α_{1}^{2}) for the current subcase. So since ζ(e) ≥ 0 always, to show that S ≥ 0 in the current subcase, it suffices to show that for “many” edges e in p, ζ(e) is “sufficiently large” so that ∑_{e∈p} ζ(e) ≥ α_{1} − α_{1}^{2}. The existence of these edges in p will follow from the existence of the 2/γ − 1 consecutive overloaded edges in p′.

Assume without loss of generality that 2/γ − 1 = 4q for some integer q and let f_{1},...,f_{4q} be, in order, the 4q consecutive overloaded edges in p′(recall that p′is the path from s to t in G and defined by the bracing edges of p). Let U = {e_{i_{1}},...,e_{i_{4q}}} be the set of edges in p whose bracing edges correspond to f_{1},...,f_{4q} (where e_{i_{j}} corresponds with f_{j}). Note that the edges in U need not occur consecutively in p. However, using arguments similar to those used in Proposition 4.10 we can prove the following fact:

Fact 4.11. The edges of p′can be divided into two consecutive walks p′_{1} and p′_{2} (i.e., all edges in p′_{1} and p′_{2} are consecutive and all edges in p′_{2} either all occur before or after all edges in p′_{1}) such that if U_{i} ⊆ U denotes the edges of p whose bracing edges form the walk p′_{i}, then the order in p of the edges U_{1} is the same as the order of the corresponding bracing edges in p′_{1}, while the order in p of the edges U_{2} is the reverse of the order of the corresponding bracing edges in p′_{2}.

Example 4.12. Suppose p = Y_{11}-Y_{12}-Y_{13}-Y_{16}-Y_{46}-Y_{56}. The corresponding walk p′is 5-4-1-2-3-6 and the division guaranteed by the above Fact has p′_{1} = 1-2-3-6, p′_{2} = 5-4-1.

Let p′_{1}, p′_{2} be the division of p′and U_{1}, U_{2} the corresponding subsets of U for these paths, respectively, guaranteed by Fact 4.11 for p′. Without loss of generality, assume that the length of p′_{1} is at least 2q. In particular, assume without loss of generality that i_{1} < ···< i_{2q}. (If instead p′_{2} has length greater than 2q, then we assume without loss of generality that i_{2q+1} > ···> i_{4q} and the arguments below are modified accordingly.)

Let B = {1,3,5,...,2q − 1}. Fix some j ∈ B and consider the pair e_{i_{j}},e_{i_{j+1}} of edges from U. Suppose e_{i_{j}} = {Y_{ab},Y_{ac}}, e_{i_{j+1}} = {Y_{uv},Y_{uw}} where u ≠ a. Since the bracing edges for these two edges are consecutive in p′, all edges e_{ℓ} such that i_{j} < ℓ < i_{j+1} have the same bracing node (say x) and moreover, this bracing node is different from the bracing nodes in e_{i_{j}} or e_{i_{j+1}} . So we have x = c = v (Figure 4).

Let Z_{j} = ∑ ζ(e), where the sum is over e ∈ {e_{i_{j}},e_{i_{j}+1} ,e_{i_{j}+2} ,...,e_{i_{j+1} −1} ,e_{i_{j+1}} } (i.e., over the edges e_{i_{j}} and e_{i_{j+1}} , and all edges between them in p).

Claim 4.13. Z_{j} ≥ 2γ/3.

Since j ∈ B was arbitrary and |B| = q, the claim implies S_{1}+ S′_{2} ≥ q(2γ/3) ≥ 1/3 − γ/6. So since γ < 1/2 and α_{1} − α_{1}^{2} ≤ \frac{1}{4} for α_{1} ∈ [0,1], it follows that S_{1} + S′_{2} ≥ α_{1} − α_{1}^{2}, completing the proof that S ≥ 0 in this subcase.

Proof of Claim 4.13. Suppose d = i_{j+1} − i_{j} − 1 is odd (the case where d is even is similar). Moreover, assume that e_{i_{j}},e_{i_{j+1}} ∈ P (the case where they are both in N is similar). Let α_{a}+ α_{u} = 1 + D. Since e_{i_{j}} and e_{i_{j+1}} are overloaded,

ζ(e_{i_{j}}) + ζ(e_{i_{j+1}} ) = 2γ(2 − α_{u}− α_{a}) = 2γ(1 − D) .  (4.26)

If D ≤ \frac{2}{3}, then (4.26) is greater than 2γ/3, and hence so is Z_{j}. So assume D > \frac{2}{3}.

Note that the bracing edges of e_{i_{j}+1} ,e_{i_{j}+2} ,...,e_{i_{j+1} −1} form a path p′′from a to u of length d in G. Let g_{1},...,g_{d+1} be the nodes on p′′where g_{1} = a, g_{d+1} = u (Figure 4). Since α satisfies the vertex cover edge constraints (4.1) for G, ∑ _{k=1}^{d+1} α_{g_{k}} ≥ (d + 1)/2. In fact, we must have that ∑ _{k=1}^{d+1} α_{g_{k}} ≥ (d + 1)/2 + D (this just says that since the endpoints of p′′sum to 1 + D then some edge(s) along p′′ must be oversatisfied by D). But then,

Z_{j} ≥ ∑_{k=1}^{(d+1)/2} ζ(e_{i_{j}+2k−1} ) = α_{c}( ∑_{k=1}^{d+1} α_{g_{k}}− \frac{d + 1}{2} ) ≥ ( \frac{1}{2} + γ) D > \frac{2γ}{3} .

Subcase 2: {s,t} is not a distant pair: Let S_{st} be the contribution of Y_{st} to S_{2} (i.e., S_{st} = δ(s,t) if v_{r} is a positive endpoint and S_{st}= β(s,t) if v_{r} is negative). Since the contribution of Y_{11} to S_{2} is −α_{1}, it follows that S_{2} = S_{st}− α_{1}.

For an edge e_{ℓ} = {Y_{ij},Y_{ik}}∈ p, let

T_{ℓ} = \{ \begin{matrix}a(i,j,k), & if e_{ℓ} ∈ P \\ b(i,j,k), & if e_{ℓ} ∈ N \end{matrix}

Recall that v_{0},v_{1}...,v_{r} are the nodes visited by the walk p and that e_{i} denotes the edge traversed between v_{i−1} and v_{i}. Note then that S_{1} = ∑ _{ℓ=1}^{r} T_{ℓ}. Moreover, recall that we have assumed without loss of generality that v_{0} = Y_{11} and v_{r} = Y_{st}. So since e_{1} ∈ P, the following claim implies S_{st}+ ∑ _{ℓ=1}^{r} T_{ℓ} ≥ α_{1}, and hence that S ≥ 0 in this subcase.

S. Arora, B. Bollobás, L. Lovász, I. Tourlakis

Figure 4: A portion of a walk p in H in which the bracing node (in this case c) does not change between edges e_{i_{j}},e_{i_{j+1}} , together with the path p′′of bracing edges in G for the portion of p with bracing node c.

Theory of Computing, Volume 2 (2006), pp. 19–52 46

Claim 4.14. Let 1 ≤ q ≤ r and suppose v_{q−1} = Y_{ij}, v_{q} = Y_{ik} (i.e., e_{q} = {Y_{ij},Y_{ik}} ). Then S_{st}+ ∑ _{ℓ=q}^{r} T_{ℓ} is at least min(α_{i},α_{j}) if e_{q} ∈ P and is at least min(0,1 − α_{i}− α_{j}) if e_{q} ∈ N.

Proof. By “backward” induction on q. For the base case q = r, assume without loss of generality that v_{q−1} = Y_{sj}, so that e_{q} = {Y_{sj},Y_{st}}. If e_{q} ∈ N, then T_{1} = −α_{s} so that T_{1}+ S_{st} = −α_{s}+ min(α_{s},α_{t}). Since α satisfies the edge constraints (4.1), it follows that α_{j} + α_{t} ≥ 1 for the bracing edge {j,t}. Hence, T_{1}+ S_{st} ≥ min(0,1 − α_{j} − α_{s}). If instead e_{q} ∈ P, then T_{1} = α_{s}+ (α_{j} + α_{t}− 1) so that

T_{1}+ S_{st} = [α_{s}+ (α_{j} + α_{t}− 1)] + (1 − α_{s}− α_{t}) = α_{j} .

The base case q = r follows.

Assume the claim holds for e_{q} and consider e_{q−1} = {Y_{ij},Y_{ik}} where v_{q−2} = Y_{ij} and v_{q−1} = Y_{ik}. If e_{q−1} ∈ N, then T_{q−1} = −α_{i}. Moreover, e_{q} ∈ P and by induction,

S_{st}+ ∑_{ℓ=q}^{r} T_{ℓ} ≥ min(α_{i},α_{k}) .

Since α satisfies the edge constraints (4.1), it follows that α_{j} +α_{k}≥ 1 for the bracing edge {j,k}. Hence,

S_{st}+ ∑_{ℓ=q−1}^{r} T_{ℓ} ≥ min(0,1 − α_{i}− α_{j}) .

If instead e_{q−1} ∈ P, then T_{q−1} = α_{i}+ (α_{j} + α_{k}− 1). Moreover, e_{q} ∈ N and by induction,

S_{st}+ ∑_{ℓ=q}^{r} T_{ℓ} ≥ min(0,1 − α_{i}− α_{k}) .

So since α_{j} + α_{k} ≥ 1, it follows that

S_{st}+ ∑_{ℓ=q−1}^{r} T_{ℓ} ≥ min(α_{i},α_{j}) .

The claim follows for e_{q−1} .

Case 3: Both endpoints of p are positive diagonal

Since p contains two diagonal vertices, Proposition 4.10 implies that there is a cycle C in the subgraph of G induced by the bracing edges corresponding to the edges in p. Since girth(G) ≥ 4R^{(m)}, it follows that C contains a distant pair. But then, as there are two different paths between this pair along C, Remark 4.8 implies that there are two subpaths p′_{1} and p′_{2} in C each consisting of 2/γ overloaded edges.

Recall that in subcase 1 of Case 2 where there was one positive diagonal vertex, one such subpath was used to argue that S ≥ 0 in that subcase. In the current case where there are two positive diagonals and the two subpaths p′_{1} and p′_{2}, the same argument then implies that S ≥ 0 for the current case also.

5 Discussion

As mentioned earlier, the interesting open problems are to extend our techniques to problems other than vertex cover and to semidefinite relaxations instead of linear relaxations. We also feel that the lower bound for the LS procedure should extend to more than logn rounds but the argument seems to need some property other than high girth.

As mentioned in our related work section, since the appearance of the conference version of this paper, a few other papers [6, 1, 30] have addressed questions introduced here. However, the techniques in all the above papers do not seem to apply to graph vertex cover. Furthermore, they also do not apply to a lift-and-project method of Sherali-Adams [28] that was contemporaneous to Lovász-Schrijver.

Acknowledgements

The first author would like to thank Noga Alon for drawing his attention to the Erdős results of [2, 13] and their tightenings, and to Subhash Khot for useful discussions.

We would also like to thank Joseph Cheriyan and Fei Qian for letting us know about the error in the proof of the LS lower bound in the conference version of this paper.

Finally we would like to thank the anonymous referees for their careful reading of our manuscript and for their many suggestions on improving this paper.

References

[1] * Mikhail Alekhnovich, Sanjeev Arora, and Iannis Tourlakis: Towards strong nonapproximability results in the Lov ász-Schrijver hierarchy. In Proceedings of the 37th Annual Symposium on the Theory of Computing, New York, May 2005. ACM Press. [STOC:1060590.1060634]. 1, 1, 5

[2] * Noga Alon and Joel H. Spencer: The probabilistic method. Wiley, New York, 1992. 2, 2.1, 5

[3] * Sanjeev Arora, Béla Bollobás, and László Lovász: Proving integrality gaps without knowing the linear program. In Proceedings of the 43rd Symposium on Foundations of Computer Science (FOCS-02), pp. 313–322, Los Alamitos, November 16–19 2002. [FOCS:10.1109/SFCS.2002.1181954]. 2, 3, 4.4

[4] * Béla Bollobás: Modern graph theory, volume 184 of Graduate Texts in Mathematics. Springer-Verlag, Berlin, 1998. 4

[5] * Maria Bonet, Toniann Pitassi, and Ran Raz: Lower bounds for cutting planes proofs with small coefficients. The Journal of Symbolic Logic, 62(3):708–728, September 1997. 1 [6] * Joshua Buresh-Oppenheim, Nicola Galesi, Shlomo Hoory, Avner Magen, and

Toniann Pitassi: Rank bounds and integrality gaps for cutting planes procedures. In Proceedings: 44th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2003, 11–14 October 2003, Cambridge, Massachusetts, pp. 318–327. pub-IEEE, 2003. 1, 1, 4, 5

[7] * Joseph Cheriyan and Fei Qian: Personal communication, 2005. 2

[8] * Vasek Chvátal: Edmonds polytopes and a hierarchy of combinatorial problems. Discrete Math., 4:305–337, 1973. 1

[9] * William Cook and Sanjeeb Dash: On the matrix-cut rank of polyhedra. Mathematics of Operations Research, 26(1):19–30, 2001. 1

[10] * Irit Dinur, Venkatesan Guruswami, Subhash Khot, and Oded Regev: A new multilayered PCP and the hardness of hypergraph vertex cover. In ACM, editor, Proceedings of the Thirty-Fifth ACM Symposium on Theory of Computing, San Diego, CA, USA, June 9–11, 2003, pp. 595–601, New York, NY, USA, 2003. ACM Press. [STOC:780542.780629]. 1

[11] * Irit Dinur and Shmuel Safra: On the hardness of approximating minimum vertex cover. Annals of Mathematics, 162(1), 2005. 1

[12] * Paul Erdös: Graph theory and probability. Canadian Journal of Mathematics, 11:34–38, 1959. 4

[13] * Paul Erdös: On circuits and subgraphs of chromatic graphs. Mathematika, 9:170–175, 1962. 2, 5

[14] * Uriel Feige: Randomized graph products, chromatic numbers, and the Lovász ϑ-function. Combinatorica, 17(1):79–90, 1997. [Combinatorica:x785787h43724566]. 2.2, 2.15

[15] * Uriel Feige: A threshold of lnn for approximating set cover. Journal of the ACM, 45(4):634– 652, 1998. [JACM:285055.285059]. 1

[16] * Uriel Feige and Robert Krauthgamer: The probable value of the Lovász–Schrijver relaxations for maximum independent set. SIAM Journal on Computing, 32(2):345–370, 2003. [SICOMP:10.1137/S009753970240118X]. 1

[17] * Michel X. Goemans: Worst-case comparison of valid inequalities for the TSP. Mathematical Programming, 69:335–349, 1995. [MathProg:n25193135v44l625]. 1

[18] * Michel X. Goemans and Levent Tunçel: When does the positive semidefiniteness constraint help in lifting procedures? Mathematics of Operations Research, 26(4):796–815, 2001. 1

[19] * Michel X. Goemans and David P. Williamson: .878-approximation algorithms for MAX CUT and MAX 2SAT. In Proceedings of the 26th Annual ACM Symposium on Theory of Computing, STOC’94 (Montréal, Québec, Canada, May 23-25, 1994), pp. 422–431, New York, 1994. ACM Press. [STOC:195058.195216]. 1 [20] * Johan Håstad: Some optimal inapproximability results. Journal of the ACM, 48(4):798–859,

2001. [JACM:258533.258536]. 1

[21] * Dorit Hochbaum: Approximating covering and packing problems: Set cover, vertex cover, independent set, and related problems. In Approximation Algorithms for NP-hard Problems. PWS Publishing Company, 1997. 1

[22] * Dorit Hochbaum, editor. Approximation Algorithms for NP-hard Problems. PWS Publishing Company, 1997. 1

[23] * László Lipták and László Lovász: Critical facets of the stable set polytope. Combinatorica, 21(1):61–88, 2001. [Combinatorica:8hmkpcvb5qaw5dnv]. 1, 3

[24] * László Lovász and Alexander Schrijver: Cones of matrices and set-functions and 0-1 optimization. SIAM Journal on Optimization, 1(2):166–190, May 1991. [SIOPT:01/0801013]. 1, 3, 4, 4, 4.1, 4.4, 4.4

[25] * Christos H. Papadimitriou and Santosh Vempala: On the approximability of the Traveling Salesman problem. In Proceedings of the 32nd Annual ACM Symposium on Theory of Computing, STOC’2000 (Portland, Oregon, May 21-23, 2000), pp. 126–133, New York, 2000. ACM Press. [STOC:335305.335320]. 1

[26] * Fei Qian: The integrality gap of the minimum vertex cover problem. Master’s thesis, University of Waterloo, 2003. 2

[27] * Alexander A. Razborov: Lower bounds on the monotone complexity of some Boolean functions. Dokl. Akad. Nauk SSSR, 281(4):798–801, 1985. In Russian: English translation in Soviet Math. Dokl. 31:354–357, 1985. 1

[28] * Hanif D. Sherali and Warren P. Adams: A hierarchy of relaxations between the continuous and convex hull representations for zero-one programming problems. SIAM Journal on Discrete Mathematics, 3(3):411–430, August 1990. [SIDMA:03/0403036]. 5

[29] * David B. Shmoys: Cut problems and their application to divide-and-conquer. In Approximation Algorithms for NP-hard Problems. PWS Publishing Company, 1997. 1

[30] * Iannis Tourlakis: Towards optimal integrality gaps for hypergraph vertex cover in the Lovász-Schrijver hierarchy. In 8th. International Workshop on Approximation Algorithms for Combinatorial Optimization Problems and 9th International Workshop on Randomization and Computation, pp. 233–244, 2005. 1, 1, 5

[31] * Vijay V. Vazirani: Approximation Algorithms. Springer-Verlag, Berlin, 2001. 1

[32] * Laurence A. Wolsey: Heuristic analysis, linear programming, and branch and bound. Mathematical Programming Studies, 13:121–134, 1980. 1 [33] * Mihalis Yannakakis: Expressing combinatorial optimization problems by linear pro-

grams. Journal of Computer and System Sciences, 43(3):441–466, December 1991. [JCSS:10.1016/0022-0000(91)90024-Y]. 1

AUTHORS

Sanjeev Arora [About the author]

professor Department of Computer Science Princeton University Princeton, NJ 08544 arora cs princeton edu

http://www.cs.princeton.edu/~arora

Béla Bollobás [About the author]

professor University of Memphis, TN 38152, U.S.A., and Trinity College, Cambridge, U.K. bollobas msci memphis edu and b bollobas dpmms cam ac uk

László Lovász [About the author]

senior research associate Microsoft Research One Microsoft Way, Redmond, WA 98052-6399 lovasz microsoft com

Iannis Tourlakis [About the author]

graduate student Department of Computer Science Princeton University Princeton, NJ 08544 itourlak cs princeton edu

http://www.cs.princeton.edu/~itourlak

ABOUT THE AUTHORS

Sanjeev Arora obtained his Ph.D. from the University of California at Berkeley in 1994 under the supervision of Umesh Vazirani. He has been at Princeton University since 1994 where he is professor of Computer Science. His research area is Theoretical Computer Science, specifically, Computational Complexity, uses of randomness in computation, Probabilistically Checkable Proofs (PCPs), computing approximate solutions to NP-hard problems, and geometric embeddings of metric spaces. He was a co-winner of the 1995 ACM Dissertation award. For his work on PCPs he was a cowinner of the 2001 Gödel Prize. He spends his spare time with his two kids, and doing black and white photography in his darkroom.

Béla Bollobás is a student of Paul Erdős, and received doctorates from Budapest, Hungary, and Cambridge, England. He has been in Cambridge since 1969, where he is a Senior Research Fellow of Trinity College, and for the past decade he has held the Jabie Hardin Chair of Excellence in Graph Theory and Combinatorics at the University of Memphis. He works mostly in Combinatorics, Graph Theory and Percolation Theory, and has published over 300 research papers and eight books, including Extremal Graph Theory, Random Graphs, and Modern Graph Theory. He has had over thirty Ph.D. students. He is a Foreign Member of the Hungarian Academy of Sciences, and was an invited speaker at the ICM in 1998.

László Lovász received his doctorate from the Eötvös Loránd University in Budapest, Hungary, where his advisor was Tibor Gallai. He is a member of the Hungarian Academy of Sciences. He received the George Pólya Prize of the Society for Industrial and Applied Mathematics (1979), the Delbert Ray Fulkerson Prize of the American Mathematical Society and the Mathematical Programming Society (1982), the Brouwer Medal of the Dutch Mathematical Society (1993) and the Wolf Prize (1999). He is editor-in-chief of Combinatorica and editor of 12 other Journals. His field of research is mainly in combinatorial optimization, algorithms, complexity, and random walks on graphs. He has written 4 research monographs and 3 textbooks, and about 200 research papers.

Iannis Tourlakis obtained his B.Sc. in 1998 and M.Sc. in 2000 from the University of Toronto where his M.Sc. advisor was Stephen Cook. He is currently completing his Ph.D. at Princeton University under the supervision of Sanjeev Arora. When not thinking about research (mainly lower bounds in convex optimization as well as problems in derandomization) he likes to fool around with whatever musical instrument he can get his hands on, preferably a violin or piano. Failing that, like a true Canadian he’ll settle for playing or watching some hockey.