# «A Tractable hypergraph properties for constraint satisfaction and conjunctive queries1 D´niel Marx, Computer and Automation Research Institute, ...»

Moderately connected pairs. Let us deﬁne µ such that µ(v) = 2µ0 (v) if v ∈ W and µ(v) = 0 otherwise. By Claim 1, µ is a fractional independent set. The set W is (µ0, λ)connected (recall that a subset of (µ0, λ)-connected is also (µ0, λ)-connected). However, W is not necessarily (µ, λ)-connected. In the next step, we ﬁnd a large collection of pairs (Ai, Bi ) that violate (µ, λ)-connectivity. Informally, we can say that these pairs (Ai, Bi ) are “moderately connected”: denoting wi = min{µ(Ai ), µ(Bi )}, the minimum value of a fractional (Ai, Bi )-separator for such a pair is less than λwi (because the pair (Ai, Bi ) violates (µ, λ)-connectivity), but at least λwi /2 = λ min{µ0 (Ai ), µ0 (Bi )} (because W is (µ0, λ)-connected).

** Claim 2. There are disjoint sets A1, B1,.**

.., Ar, Br ⊆ W such that for every 1 ≤ i ≤ r there is a fractional (Ai, Bi )-separator with weight less than λwi for wi := min{µ(Ai ), µ(Bi )} and r w := i=1 wi ≥ T.

Proof. Let us greedily select a maximal collection of pairs (A1, B1 ),..., (Ar, Br ) with the property that there is a fractional (Ai, Bi )-separator with weight less than λwi for wi := min{µ(Ai ), µ(Bi )}. Note that every fractional separator has value at least 1 (as W is in a single component of H), thus λwi 1 holds, implying wi 1/λ 1. We can assume that µ(Ai ), µ(Bi ) ≤ wi + 1: if, say, µ(Ai ) µ(Bi ) + 1, then removing an arbitrary vertex of Ai decreases µ(Ai ) by at most one (as µ is a fractional independent set) without changing min{µ(Ai ), µ(Bi )}, hence there would be a smaller pair of sets with the required properties.

Therefore, we have 2wi ≤ µ(Ai ∪ Bi ) ≤ 2wi + 1 ≤ 3wi for every 1 ≤ i ≤ r.

r r Suppose for contradiction that w := i=1 wi T. Let W := W \ i=1 (Ai ∪ Bi ). As r r µ( i=1 (Ai ∪ Bi )) ≤ i=1 3wi = 3w 3T, we have µ(W ) µ(W ) − 3T = 2µ0 (W ) − 3T ≥ 2 conλ (H) − 2k − 3T ≥ conλ (H). Since the greedy selection stopped, there is no fractional (A, B )-separator of value less than λ · min{µ(A ), µ(B )} for any disjoint A, B ⊆ W, that is, W is (µ, λ)-connected with µ(W ) conλ (H), contradicting the deﬁnition of conλ (H).

Finding a multicommodity ﬂow. Let (A1, B1 ),..., (Ar, Br ) be as in Claim 2. Since there is a fractional (Ai, Bi )-separator of value less than λwi, the maximum value of a µdemand multicommodity ﬂow between pairs (A1, B1 ),..., (Ar, Br ) is less than λw. Let y be an optimum dual solution; we give a lower bound on the total weight of the edge variables.

Locating the cliques. Let y be an optimum dual solution for the maximum multicommodity ﬂow problem with pairs (A1, B1 ),..., (Ar, Br ) and let ﬂow F be the sum of the ﬂows obtained from an optimum primal solution.

** Claim 4. There are k pairwise-disjoint cliques K1,.**

.., Kk and a set of k subﬂows f1,..., fk of F, each of them having value at least 1/2, such that every path appearing in fi intersects Ki and is disjoint from Kj for every j = i.

Proof. Let F (0) = F and for i = 1, 2,..., let F (i) be the ﬂow obtained from F (0) by removing f1,..., fi. Let c(e, F (i) ) be the total weight of the paths in F (i) intersecting edge e and let Ci = e∈E(H) y(e)c(e, F (i) ). By complementary slackness, c(e, F (0) ) = 1 for each e ∈ E(H) with y(e) 0 and hence C0 = e∈E(H) y(e) ≥ 2k.

**Let us select ei to be an edge such that c(ei, F (i−1) ) is maximum possible and let Ki :=**

i−1 ei \ j=1 ej. Let the ﬂow fi contain all the paths of F (i−1) intersecting ei. Observe that the paths appearing in fi do not intersect e1,..., ei−1 (otherwise they would be in one of f1,..., fi−1 and hence they would no longer be in F (i−1) ), thus clique Ki intersects every path in fi.

For every u − v path P appearing in F (0), we get e∈E(H),e∩P =∅ y(e) + y(u) + y(v) = 1 from complementary slackness: if the primal variable corresponding to P is nonzero, then the corresponding dual constraint is tight. In particular, this means that the total weight of the edges intersecting such a path P is at most 1 in y. As F (i−1) is a subﬂow of F (0), this is also true for every path P in F (i−1). This means that when we remove a path of weight γ from F (i−1) to obtain F (i), then the total weight of the edges e for which c(e, F (i−1) ) decreases by γ is at most 1, i.e., Ci−1 decreases by at most γ. As only the paths intersecting ei are removed from F (i−1) and the total weight of the paths intersecting ei is at most 1, we get that Ci ≥ Ci−1 − 1 and hence Ci ≥ C0 − k ≥ C0 /2 for i ≤ k. Since C0 = e∈E(H) y(e) and Ci = e∈E(H) y(e)c(e, F (i) ) ≥ C0 /2, it follows that there has to be at least one edge e with c(e, F (i) ) ≥ 1/2. Thus in each step, we can select an edge ei such that that the total

** Claim 5. There is a fractional independent set µ such that U is a (µ, λ/6)-connected set with µ (Ki ) ≥ 1/2 for every 1 ≤ i ≤ r.**

Proof. Each path P in fi is a path with endpoints in W and intersecting Ki. Let us truncate each path P in fi such that its ﬁrst endpoint is still in W and its second endpoint is in Ki ; let fi be the (W, Ki )-ﬂow obtained by truncating every path in fi. Note that fi is still a ﬂow and the sum F of f1,..., fk is a (W, U )-ﬂow. Let µ1 = µ and let µ2 (v) be the total weight of the paths in F with second endpoint v. It is clear that µ2 is a fractional independent set, µ2 (Ki ) ≥ 1/2, and F is a (µ1, µ2 )-demand (W, U )-ﬂow with value µ2 (U ).

Thus by Lemma 6.4, U is a (µ2, λ/6)-connected set with the required properties.

The set U, the partition (K1,..., Kr ), and the fractional independent set µ clearly satisfy the requirements of the lemma.

6.2. Concurrent ﬂows and embedding Let W be a set of vertices and let (X1,..., Xk ) be a partition of W. A uniform concurrent ﬂow of value on (X1,..., Xk ) is a compatible set of k ﬂows Fi,j (1 ≤ i j ≤ k) where Fi,j is an (Xi, Xj )-ﬂow of value. The maximum value of a uniform concurrent ﬂow on W can be expressed as the optimum values of the primal and dual linear programs in Figure 6.

Intuitively, the dual linear program expresses that the “distance” of Xi and Xj is at least i,j (where distance is measured as the minimum total weight of the edges intersected by an Xi − Xj path) and the sum of these k distances is at least 1.

If H is connected, then the maximum value of a uniform concurrent ﬂow on (X1,..., Xk ) is at least 1/ k = Ω(k −2 ): if each of the k ﬂows has value 1/ k, then they are clearly compatible. The following lemma shows that in a (µ, λ)-connected set, if the sets X1,..., Xk are cliques and µ(Xi ) ≥ 1/2 for every i, then we can guarantee a better bound of Ω(k − 2 ).

** Lemma 6.6.**

Let H be a hypergraph, µ a fractional independent set of H, and W ⊆ V (H) a (µ, λ)-connected set for some 0 λ 1. Let (K1,..., Kk ) (for some k ≥ 1) be a partition of W such that Ki is a clique and µ(Ki ) ≥ 1/2 for every 1 ≤ i ≤ k. Then there is a uniform concurrent ﬂow of value Ω(λ/k 2 ) on (K1,..., Kk ).

Journal of the ACM, Vol. V, No. N, Article A, Publication date: January YYYY.

A:38 D. Marx Proof. Suppose that there is no uniform concurrent ﬂow of value β · λ/k 2, where β 0 is a suﬃciently small universal constant speciﬁed later. This means that the dual linear program has a solution having value less than that. Let us ﬁx such a solution (y, i,j )

**of the dual linear program. In the following, for every path P, we denote by y(P ) :=**

e∈E(H),e∩P =∅ y(e) the total weight of the edges intersecting P. It is clear from the dual linear program that y(P ) ≥ i,j for every P ∈ Pi,j.

We construct two graphs G1 and G2 : the vertex set of both graphs is {1,..., k} and for every 1 ≤ i j ≤ k, vertices i and j are adjacent in G1 (resp., G2 ) if and only if i,j 1/(3k ) (resp., i,j 1/k ). Note that G2 is a subgraph of G1. First we prove the

**following claim:**

** Claim 1. If the distance of u and v is at most 3 in the complement of G1, then u and v are not adjacent in G2.**

Proof. Suppose that uw1 w2 v is a path of length 3 in the complement of G1 (the same argument works for paths of length less than 3). By deﬁnition of G1, there is a Ku − Kw1 path P1, a Kw1 − Kw2 path P2, and a Kw2 − Kv path P3 such that y(P1 ), y(P2 ), y(P3 ) ≤ 1/(3k 2 ). Since Kw1 and Kw2 are cliques, paths P1 and P2 touch, and paths P2 and P3 touch. Thus by concatenating the three paths, we can obtain a Ku − Kv path P with y(P ) ≤ y(P1 ) + y(P2 ) + y(P3 ) ≤ 1/k 2, implying that u and v are not adjacent in G2, proving the claim. Note that the proof of this claim is the only point where we use that the Ki ’s are cliques.

E(H) → R+ be deﬁned by y (e) := 3k 2 · y(e), thus y has total weight less Let y : √ than 3β · λ k. Suppose ﬁrst that G1 has a matching a1 b1,..., am bm of size m = k/4.

This means that y covers every Kai − Kbi path for every 1 ≤ i ≤ k/4. Therefore, by √ k/4 · (1/2) 3β ·λ k, if β is suﬃciently small, Lemma 6.3, y has weight at least (λ/7)· yielding a contradiction.

Thus the size of the maximum matching in G1 is less than k/4, which means that there is a vertex cover S1 of size at most k/2. Let S2 ⊆ S1 contain those vertices of S1 that are adjacent to every vertex outside S1 in G1. We claim that S2 is a vertex cover of G2. Suppose that there is an edge uv of G2 for some u, v ∈ S2. By the deﬁnition of S2, either u ∈ S1, or there is a vertex w1 ∈ S1 such that u and w1 are not adjacent in G1. Similarly, either v is not in S1, or it is not adjacent in G1 to some w2 ∈ S1. Since vertices not in S1 are not adjacent in G1 (as S1 is a vertex cover of G1 ), we get that the distance of u and v is at most 3 in the complement of G1. Thus by the claim, u and v are not adjacent in G2.

Let us give an upper bound on 1≤ij≤k i,j by bounding i,j separately for pairs that are adjacent in G2 and for pairs that are not adjacent in G2. The number of edges in G2 is at most |S2 |k (as S2 is vertex cover). The total weight of y, which is less than β · λ/k 2, is an upper bound on any i,j. Furthermore, if i and j are not adjacent in G2, then we have i,j ≤ 1/k. Therefore,

Intuitively, the intersection structure of the paths appearing in a uniform concurrent ﬂow on cliques K1,..., Kk is reminiscent of the edges of the complete graph on k vertices: if {i1, j1 } ∩ {i2, j2 } = ∅, then every path of Fi1,j1 touches every path of Fi2,j2. We use the following result from [Marx 2010b], which shows that the line graph of cliques have good embedding properties. If G is a graph and q ≥ 1 is an integer, then the blow up G(q) is obtained from G by replacing every vertex v with a clique Kv of size q and for every edge uv of G, connecting every vertex of the clique Ku with every vertex of the clique Kv. Let Lk be the line graph of the complete graph on k vertices.

** Lemma 6.7 (Marx [2010b]).**

For every k 1 there is a constant nk 0 such that (q) for every G with |E(G)| nk and no isolated vertices, the graph G is a minor of Lk for q = 130|E(G)|/k 2. Furthermore, a minor mapping can be found in time polynomial in the size of G.

(q) Using the terminology of embeddings, a minor mapping of G into Lk can be considered as an embedding from G to Lk where every vertex of Lk appears in the image of at most q vertices, i.e., the vertex depth of the embedding is at most q. Thus we can restate Lemma 6.7

**the following way:**

** Lemma 6.8.**

For every k 1 there is a constant nk 0 such that for every G with |E(G)| nk and no isolated vertices, the graph G has an embedding into Lk with vertex depth O(|E(G)|/k 2 ). Furthermore, such an embedding can be found in time polynomial in the size of G.

**Now we are ready to prove Theorem 6.1, the main result of the section:**

Proof (of Theorem 6.1). By Lemma 6.5 and Lemma 6.6, for some k = Ω(λ conλ (H)), there are cliques K1,..., Kk and a uniform concurrent ﬂow Fi,j (1 ≤ i j ≤ k) of value = Ω(λ/k 2 ) on (K1,..., Kk ). By trying all possibilities for the cliques and then solving the uniform concurrent ﬂow linear program, we can ﬁnd these ﬂows (the time required for this step is a constant f (H, λ) depending only on H and λ). Let w0 be the smallest positive weight appearing in the ﬂows.

Let m = |E(G)| and suppose that m ≥ nk, for the constant nk in Lemma 6.8. Thus the algorithm of Lemma 6.8 can be used to ﬁnd a an embedding ψ from G to Lk with vertex depth q = O(m/k 2 ). Let us denote by v{i,j} (1 ≤ i j ≤ k) the vertices of Lk with the meaning that distinct vertices v{i1,j1 } and v{i2,j2 } are adjacent if and only if {i1, j1 } ∩ {i2, j2 } = ∅.

We construct an embedding φ from G to H the following way. The set φ(u) ⊆ V (H) is obtained from the set ψ(u) ⊆ V (Lk ) by replacing each vertex of v{i,j} ∈ ψ(u) ⊆ V (Lk ) by a path from the ﬂow Fi,j (thus φ(u) is the union of |ψ(u)| paths of H). We select the paths in such a way that the following requirement is satisﬁed: a path P of Fi,j having weight w is selected into the image of at most (q/ ) · w vertices of G. We set mH,λ suﬃciently large that (q/ ) · w0 ≥ 1 (note that q depends on m, but and w0 depends only on H and λ). Thus if m ≥ mH,λ, then (q/ ) · w ≤ 2(q/ ) · w. Since the total weight of the paths in Fi,j is, these paths can accommodate the image of at least (q/ ) · = q vertices. As each vertex v{i,j} of Lk appears in the image of at most q vertices of G in the mapping ψ, we can satisfy the requirement.

It is easy to see that if u1 and u2 are adjacent in G, then φ(u1 ) and φ(u2 ) touch: in this case, there are vertices v{i1,j1 } ∈ ψ(u1 ), v{i2,j2 } ∈ ψ(u2 ) that are adjacent or the same in Lk (that is, there is a t ∈ {i1, j1 } ∩ {i2, j2 }), and the corresponding paths of Fi1,j1 and Fi2,j2 selected into φ(u1 ) and φ(u2 ) touch, as they both intersect the clique Kt. With a similar argument, we can show that φ(u) is connected.