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

Let directed graph D be the orientation of the primal graph of H such that if vi and vj are adjacent and i j, then there is a directed edge −→ in D. Figure 3 shows a directed v− j iv

Fig. 4. Proof of Claim 2: Two examples of directed paths where every vertex has the same class κ (and h := 2−κ ). The shaded lines show the oﬀsets of the vertices.

path in D. If P is a directed path in D, then the width of P is the length of the interval v∈P ι(v) (note that by Claim 1, this union is indeed an interval). The following claim

**bounds the maximum possible width of a directed path:**

** Claim 2. If P is a directed path D starting at v, then the width of P is at most 16x(v).**

Proof. We ﬁrst prove that if every vertex of P has the same class κ(v), then the width of P is at most 4 · 2−κ(v). Since the class is nondecreasing along the path, we can partition the path into subpaths such that every vertex in a subpath has the same class and the classes are distinct on the diﬀerent subpaths. The width of P is at most the sum of the widths of the subpaths, which is at most i≥κ(v) 4 · 2−i = 8 · 2−κ(v) ≤ 16x(v).

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

A:28 D. Marx Suppose now that every vertex of P has the same class κ(v) as the ﬁrst vertex v and let h := 2−κ(v). As the oﬀset is nondecreasing, path P can be partitioned into two parts: a subpath P1 containing vertices with oﬀset less than h, followed by a subpath P2 containing vertices with oﬀset at least h (one of P1 and P2 can be empty). See Figure 4 for examples.

We show that each of P1 and P2 has width at most 2h, which implies that the width of P is at most 4h. Observe that if u ∈ P1 and ι(u) contains a point i · 2h − h for some integer i, then, considering x(u) ≤ h and the bounds on the oﬀset of u, this is only possible if ι(u) = [i · 2h − h, i · 2h], i.e., i · 2h − h is the left endpoint of ι(u). Thus if I1 = u∈P1 ι(u) contains i · 2h − h, then it is the left endpoint of I1. Therefore, I1 can contain i · 2h − h for at most one value of i, which immediately implies that the length of I1 is at most 2h.

We argue similarly for P2. If u ∈ P2, then ι(u) can contain the point i · 2h only if ι(u) = [i · 2h, i · 2h + h]. Thus if I2 = u∈P2 ι(u) contains i · 2h, then it is the left endpoint of I2. We get that I2 can contain i · 2h for at most one value of i, which immediately implies that the width of I2 is at most 2h. This concludes the proof of Claim 2.

Let c(v) := ∂bπ (v).

Proof. Let us examine the contribution of an edge e ∈ E(H) with value s(e) to the sum.

For every vertex v ∈ e, edge e increases the value x(v) by at most s(e) (the contribution may be less than s(e), since we deﬁned x(v) to be at most 1). Thus the total contribution of edge e is at most

where the ﬁrst inequality follows Prop. 5.2(5); the last equality follows form Prop. 5.2(3);

the last inequality follows from the fact that b is edge dominated. Therefore, v∈V (H) x(v)c(v) ≤ e∈E(H) s(e) ≤ w, proving Claim 3.

Let S be a set of vertices. We deﬁne S to be the “inneighbor closure” of S, that is, the set of all vertices from which a vertex of S is reachable on a directed path in D (in particular, this means that S ⊆ S).

Let S(t) be the set of all vertices v ∈ V (H) for which t ∈ ι(v). Observe that for every 0 ≤ t ≤ 1, the set S(t) (and hence S(t)) separates X from Y. We use an averaging argument to show that there is a 0 ≤ t ≤ 1 for which bπ (S(t)) is O(w). As b∗ (S(t)) ≤ bπ (S(t)) by deﬁnition, the set S(t) satisﬁes the requirement of the lemma.

If we are able to show that 0 bπ (S(t))dt = O(w), then the existence of the required t clearly follows. Let Iv (t) = 1 if v ∈ S(t) and let Iv (t) = 0 otherwise. If Iv (t) = 1, then there is a path P in D from v to a member of S(t). By Claim 2, the width of this path is at most

(we used Claim 4 in the ﬁrst equality and Claim 3 in the last inequality).

Although it is not used in this paper, we can prove the converse of Theorem 5.7 in a very simple way.

** Theorem 5.8.**

Let H be a hypergraph, and let X, Y ⊆ V (H) be two sets of vertices.

Suppose that for every edge-dominated monotone submodular function b on H with b(∅) = 0, there is an (X, Y )-separator S with b(S) ≤ w. Then there is a fractional (X, Y )-separator of weight at most w.

Proof. If there is no fractional (X, Y )-separator of weight at most w, then by LP duality, there is an (X, Y )-ﬂow F of value greater than w. Let b(Z) be deﬁned as the total weight of the paths in F intersecting Z; it is easy to see that f is a monotone submodular function, and since F is a ﬂow, b(e) ≤ 1 for every e ∈ E(H). Thus by assumption, there is an (X, Y )separator S with b(S) ≤ w. However, every X − Y path of F intersects (X, Y )-separator S, which implies b(S) w, a contradiction.

The problem of ﬁnding a small separator in the sense of Theorem 5.7 might seem related to submodular function minimization at a ﬁrst look. We close this section by pointing out that ﬁnding an (A, B)-separator S with b(S) small for a given submodular function b is not an instance of submodular function minimization, and hence the well-known algorithms (see [Iwata 2008; Iwata et al. 2001; Schrijver 2000]) cannot be used for this problem. If a submodular function g(X) describes the weight of the boundary of X, then ﬁnding a small (A, B)-separator is equivalent to minimizing g(X) subject to A ⊆ X, X ∩ B = ∅, which can be expressed as an instance of submodular function minimization (and hence solvable in polynomial time). In our case, however, b(S) is the weight of S itself, which means that we have to minimize g(S) subject to S being an (A, B)-separator and this latter constraint cannot be expressed in the framework of submodular function minimization. A possible workaround is to deﬁne δ(X) as the neighborhood of X (the set of vertices outside X adjacent to X) and b (X) := b(δ(S)); now minimizing b (X) subject to A ⊆ X ∪ δ(X), X ∩ B = ∅ is the same as ﬁnding an (X, Y )-separator S minimizing b(S). However, the function b is not necessarily a submodular function in general. Therefore, transforming b to b this way does not lead to a polynomial-time algorithm using submodular function minimization. In fact, it is quite easy to show that ﬁnding an (A, B)-separator S with b(S) minimum possible can be an NP-hard problem even if b is a submodular function of very simple form.

** Theorem 5.9.**

Given a graph G, subsets of vertices X, Y, and collection S of subsets of vertices, it is NP-hard to ﬁnd an (X, Y )-separator that intersects the minimum number of members of S.

Proof. The proof is by reduction from 3-coloring. Let H be a graph with n vertices and m edges; we identify the vertices of H with the integers from 1 to n. We construct a graph G consisting of 3n + 2 vertices, vertex sets X, Y, and a collection S of 6m sets such that there is an (X, Y )-separator S in G intersecting at most 3m members of S if and only if H is 3-colorable.

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

A:30 D. Marx The graph G consists of two vertices x, y, and for every 1 ≤ i ≤ n, a path xvi,1 vi,2 vi,3 y of length 4 connecting x and y. The collection S is constructed such that for every edge ij ∈ E(H) and 1 ≤ a, b ≤ 3, a = b, there is a corresponding set {vi,a, vj,b, x, y}. Let X := {x} and Y := {y}. Observe that the set {vi,a, vj,b } intersects exactly 3 sets of S if a = b and exactly 4 sets of S if a = b.

Let c : V (H) → {1, 2, 3} be a 3-coloring of H. The set S = {vi,c(i) | 1 ≤ i ≤ n} is clearly an (X, Y )-separator. For every ij ∈ E(H), separator S intersects only 3 of the 6 sets {vi,a, vi,b, x, y}. Therefore, S intersects exactly 3m members of S.

Consider now an (X, Y )-separator S intersecting at most 3m members of S. Since every member of S contains both x and y, it follows that x, y ∈ S. Thus S has to contain at least one internal vertex of every path xvi,1 vi,2 vi,3 y. For every 1 ≤ i ≤ n, let us ﬁx a vertex vi,c(i) ∈ S. We claim that c is a 3-coloring of H. For every ij ∈ E(H), S intersects at least 3 of the sets {vi,a, vi,b, x, y}, and intersects 4 of them if c(i) = c(j). Thus the assumption that S intersects at most 3m members of S immediately implies that c is a proper 3-coloring.

5.3. Obtaining a highly connected set The following lemma is the same as the main result of Section 5 (Theorem 5.1) we are trying to prove, with the exception that b-width is replaced by b∗ -width. By Prop 5.2(2), b∗ (S) ≥ b(S) for every set S ⊆ V (H), thus b∗ -width is not less than b-width. Therefore, the following is actually a stronger statement and immediately implies Theorem 5.1.

** Lemma 5.10.**

For every suﬃciently small constant λ 0, the following holds. Let b be an edge-dominated monotone submodular function of H with b(∅) = 0. If the b∗ -width of H is greater than 3 (w + 1), then conλ (H) ≥ w.

Proof. Suppose that λ 1/c, where c is the universal constant of Lemma 5.7 hidden by the big-O notation. Suppose that conλ (H) w, that is, there is no fractional independent set µ and (µ, λ)-connected set W with µ(W ) ≥ w. We show that H has a tree decomposition

**of b∗ -width at most 2 (w + 1), or more precisely, we show the following stronger statement:**

For every subhypergraph H of H and every W0 ⊆ V (H ) with b∗ (W0 ) ≤ w + 1, there is a tree decomposition of H having b∗ -width at most 2 (w + 1) such that W0 is contained in one of the bags.

We prove this statement by induction on |V (H )|. If b∗ (V (H )) ≤ 2 (w + 1), then a decomposition consisting of a single bag proves the statement. Otherwise, let W be a superset of W0 such that w ≤ b∗ (W ) ≤ w + 1; let us choose a W that is inclusionwise maximal with respect to this property. Observe that there has to be at least one such set: from the fact that b∗ (v) ≤ 1 for every vertex v and from Prop. 5.2(6), we know that adding a vertex increases b∗ (W ) by at most 1. Since b∗ (V (H )) ≥ 2 (w + 1), by adding vertices to W0 in an ∗ arbitrary order, we eventually ﬁnd a set W with b (W ) ≥ w, and the ﬁrst such set satisﬁes b∗ (W ) ≤ w + 1 as well.

Let π be an ordering of V (H ) such that bπ (W ) = b∗ (W ). As in Lemma 5.3, let us deﬁne the fractional independent set µ by µ(v) := ∂bπ,W (v) if v ∈ W and µ(v) = 0 otherwise.

Clearly, we have µ(W ) = bπ (W ) = b∗ (W ) ≥ w.

By assumption, W is not (µ, λ)-connected, hence there are disjoint sets A, B ⊆ W and a fractional (A, B)-separator of weight less than λ · min{µ(A), µ(B)}. Thus by Theorem 5.7, there is an (A, B)-separator S ⊆ V (H ) with b∗ (S) c · λ · min{µ(A), µ(B)} min{µ(A), µ(B)} ≤ µ(W )/2 ≤ (w + 1)/2 (the second inequality follows from the fact that A and B are disjoint subsets of W ). Let C1,..., Cr be the connected components of H \ S;

** by Lemma 5.6, b∗ ((Ci ∩ W ) ∪ S) µ(W ) = bπ (W ) = b∗ (W ) ≤ w + 1 for every 1 ≤ i ≤ r.**

As b∗ (V (H )) ≥ 3 (w + 1) and b∗ (S) ≤ (w + 1)/2, it is not possible that S = V (H ), hence r 0. It is not possible that r = 1 either: (C1 ∩ W ) ∪ S is a proper superset of W with Journal of the ACM, Vol. V, No. N, Article A, Publication date: January YYYY.

Tractable hypergraph properties for constraint satisfaction and conjunctive queries A:31 b∗ -value strictly less than b∗ (W ) ≤ w + 1, and (as b∗ (V (H )) ≥ 2 (w + 1)) we could ﬁnd a set between (C1 ∩ W ) ∪ S and V (H ) contradicting the maximality of the choice of W.

Thus r ≥ 2, which means that each hypergraph Hi := H [Ci ∪ S] has strictly fewer vertices than H for every 1 ≤ i ≤ r.

By the induction hypothesis, each Hi has a tree decomposition Ti having b∗ -width at most 3 (w + 1) such that Wi := (Ci ∩ W ) ∪ S is contained in one of the bags. Let Bi be the bag of Ti containing Wi. We build a tree decomposition T of H by joining together the tree decompositions T1,..., Tr : let B0 := W0 ∪ S be a new bag that is adjacent to bags B1,..., Br. It can be easily veriﬁed that T is indeed a tree decomposition of H. Furthermore, by Prop. 5.2(6), b∗ (B0 ) ≤ b∗ (W0 ) + b∗ (S) w + 1 + (w + 1)/2 = 2 (w + 1) and by the ∗ 3 assumptions on T1,..., Tr, every other bag has b value at most 2 (w + 1).

## 6. FROM HIGHLY CONNECTED SETS TO EMBEDDINGS

The main result of this section is showing that the existence of highly connected sets implies that the hypergraph has large embedding power. Recall from Section 2 that W is a (µ, λ)connected set for some λ 0 and fractional independent set µ if for every disjoint X, Y ⊆ W, the minimum weight of a fractional (X, Y )-separator is at least λ · {µ(X), µ(Y )}. We denote by conλ (H) the maximum value of µ(W ) taken over every fractional independent set µ and (µ, λ)-connected set W. Recall also that the edge depth of an embedding φ of G into H is the maximum of v∈V (G) |φ(v) ∩ e|, taken over every e ∈ E(H).** Theorem 6.1.**

For every suﬃciently small λ 0 and hypergraph H, there is a constant mH,λ such that every graph G with m ≥ mH,λ edges has an embedding into H with edge depth O(m/(λ 2 conλ (H))). Furthermore, there is an algorithm that, given G, H, and λ, produces such an embedding in time f (H, λ)nO(1).

**In other words, Theorem 6.1 gives a lower bound on the embedding power of H:**

Corollary 6.2. For every suﬃciently small λ 0 and hypergraph H, emb(H) = Ω(λ conλ (H)).

** Theorem 6.1 is stated in algorithmic form, since the reduction in the hardness result of Section 7 needs to ﬁnd such embeddings.**