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

Equivalently, we can say that for every disjoint A, B ⊆ W, there is an (A, B)-ﬂow of value λ · min{µ(A), µ(B)}. Recall also that conλ (H) denotes the maximum value of µ(W ) taken over every fractional independent set µ and (µ, λ)-connected set W.

The main result of this section allows us to identify a highly connected set if submodular

**width is large:**

** Theorem 5.1.**

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 2 (w + 1), then conλ (H) ≥ w.

For the proof of Theorem 5.1, we need to show that if there is no tree decomposition where b(B) is small for every bag B, then a highly connected set exists. There is a standard recursive procedure that either builds a tree decomposition or ﬁnds a highly connected set (see e.g., [Flum and Grohe 2006, Section 11.2]). Simplifying somewhat, the main idea is that if the graph can be decomposed into smaller graphs by splitting a certain set of vertices into two parts, then a tree decomposition for each part is constructed using the algorithm recursively, and the tree decompositions for the parts are joined in an appropriate way to obtain a tree decomposition for the original graph. On the other hand, if the set of vertices cannot be split, then we can conclude that it is highly connected. This high-level idea has been applied for various notions of tree decompositions [Oum and Seymour 2006; Oum 2005; Adler et al. 2007; Oum and Seymour 2007; Marx 2010a], and it turns out to be useful

**in our context as well. However, we need to overcome two major diﬃculties:**

(1) Highly connected set in our context is deﬁned as not having certain fractional separators (i.e., weight assignments). However, if we want to build a tree decomposition in a recursive manner, we need integer separators (i.e., subsets of vertices) that decompose the hypergraph into smaller parts.

(2) Measuring the sizes of sets with a submodular function b can lead to problems, since the size of the union of two sets can be much smaller than the sum of the sizes of the two sets. We need the property that, roughly speaking, removing a “large” part from a set makes it “much smaller.” For example, if A and B are components of H \ S, and both b(A) and b(B) are large, then we need the property that both of them are much smaller than b(A ∪ B). Adler [2006, Section 4.2] investigates the relation between some notion of highly connected sets and f -width, but assumes that f is additive: if A and B do not touch, then f (A∪B) = f (A)+f (B). However, for a submodular function b, there is no reason to assume that additivity holds: for example, it very well may be that b(A) = b(B) = b(A ∪ B).

To overcome the ﬁrst diﬃculty, we have to understand what fractional separation really means. The ﬁrst question is whether fractional separation is equivalent to some notion of integral separation, perhaps up to constant factors. The ﬁrst, naive, question is whether a fractional (X, Y )-separator of weight w implies that there are O(w) edges whose union is an (X, Y )-separator, i.e., there is an (X, Y )-separator S with ρH (S) = O(w). There is a simple counterexample showing that this is not true. It is well-known that for every integer k 0, there is a hypergraph Hk such that ρ∗ (Hk ) = 2 and ρ(Hk ) = k. Let V be the set of vertices of Hk and let Hk be obtained from Hk by extending it with two independent sets X, Y, each of size k, and connecting every vertex of X ∪ Y with every vertex of V. It is Journal of the ACM, Vol. V, No. N, Article A, Publication date: January YYYY.

Tractable hypergraph properties for constraint satisfaction and conjunctive queries A:23 clear that there is a fractional (X, Y )-separator of weight 2, but every (X, Y )-separator S has to fully contain at least one of X, Y, or V, implying ρH (S) ≥ k.

A less naive question is whether a fractional (X, Y )-separator with weight w in H implies that there exists an (X, Y )-separator S with ρ∗ (S) = O(w) (or at most f (w) for some H function f ). It can be shown that this is not true either: using the hypergraph family presented in [Marx 2011, Section 5], one can construct counterexamples where the minimum weight of a fractional (X, Y )-separator is a constant, but ρ∗ (S) has to be arbitrarily large H for every (X, Y )-separator S (we omit the details).

We will characterize fractional separation in a very diﬀerent way. We show that if there is a fractional (A, B)-separator of weight w, then there is an (A, B)-separator S with b(S) = O(w) for every edge-dominated monotone submodular function b. Note that this separator S can be diﬀerent for diﬀerent functions b, so we are not claiming that there is a single (A, B)-separator S that is small in every b. The converse is also true, thus this gives a novel characterization of fractional separation, tight up to a constant factor. This result is the key idea that allows us to move from the domain of submodular functions to the domain of pure hypergraph properties: if there is no (A, B)-separator such that b(S) is small, then we know that there is no small fractional (A, B)-separator, which is a property of the hypergraph H only and has no longer anything to do with the submodular function b.

To overcome the second diﬃculty, we introduce a transformation that turns a monotone submodular function b on V (H) into a function b∗ that encodes somehow the neighborhood structure of H as well. The new function b∗ is no longer monotone and submodular, but it has a number of remarkable properties, for example, b∗ remains edge dominated and b∗ (S) ≥ b(S) for every set S ⊆ V (H), implying that b∗ -width is not smaller than b-width.

The main idea is to prove Theorem 5.1 for b∗ -width instead of b-width (note that this makes the statement stronger). Because of the way b∗ encodes the neighborhoods, the second diﬃculty will disappear: for example, it will be true that b∗ (A ∪ B) = b∗ (A) + b∗ (B) if there are no edges between A and B, that is, b∗ is additive on disjoint components.

** Lemma 5.6 formulates (in a somewhat technical way) the exact property of b∗ that we will need.**

Furthermore, luckily it turns out that the result mentioned in the previous paragraph remains true with b replaced by b∗ : if there is a fractional (A, B)-separator of weight w, then there is an (A, B)-separator S such that not only b(S), but even b∗ (S) is O(w).

Thus bπ (Z) is the sum of the marginal values with respect to a given ordering, while b∗ (Z) is the smallest possible sum taken over all possible orderings. Let us prove some simple properties of the function b∗. Properties (1)–(3) and their proofs show why b∗ was deﬁned

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

Tractable hypergraph properties for constraint satisfaction and conjunctive queries A:25

**Prop. 5.2(3) implies that ∂bw,Z can be used to deﬁne a fractional independent set:**

** Lemma 5.3.**

Let H be a hypergraph and let b be an edge-dominated monotone submodular function deﬁned on V (H) with b(∅) = 0. Let W ⊆ V (H) and let π be an ordering of W.

Let us deﬁne µ(v) = ∂bπ,W (v) for v ∈ W and µ(v) = 0 otherwise. Then µ is a fractional independent set of H with µ(W ) = bπ (W ).

Proof. Let e be an edge of H and let Z := e ∩ W. We have µ(e) = µ(Z) = ∂bπ,W (Z) ≤ ∂bπ,Z (Z) = bπ (Z) = b(Z) ≤ 1, where the ﬁrst inequality follows from Prop. 5.2(4), the last equality follows from Prop. 5.2(3), and the second inequality follows from the fact that b is edge dominated.

Furthermore, we have µ(W ) = ∂bπ,W (W ) = bπ (W ).

We close this section by proving the main property of b∗ that allows us to avoid the second diﬃculty described at the beginning of Section 5. First, although it is not used directly, let

**us state that b∗ is additive on sets that are independent from each other:**

** Lemma 5.4.**

Let H be a hypergraph, let b be an edge-dominated monotone submodular function deﬁned on V (H) with b(∅) = 0, and let A, B ⊆ V (H) be disjoint sets such that there is no edge intersecting both A and B. Then b∗ (A ∪ B) = b∗ (A) + b∗ (B).

Proof. By Prop. 5.2(6), we have to show only b∗ (A ∪ B) ≥ b∗ (A) + b∗ (B). Let π be an ordering of V (H) such that bπ (A ∪ B) = b∗ (A ∪ B); we can assume that π starts with the vertices of A ∪ B. Since there is no edge that intersects both A and B, and no vertex outside − − A ∪ B precedes a vertex u ∈ A ∪ B, we have Nπ (u) ⊆ A for every u ∈ A and Nπ (u) ⊆ B for every u ∈ B. Thus ∂bπ,A∪B (u) = ∂bπ,A (u) for every u ∈ A and ∂bπ,A∪B (u) = ∂bπ,B (u) for every u ∈ B. Therefore, b∗ (A ∪ B) = bπ (A ∪ B) = bπ (A) + bπ (B) ≥ b∗ (A) + b∗ (B), what we had to show.

The actual statement that we use is more complicated than Lemma 5.4: there can be edges between A and B, but we assume that there is a small (A, B)-separator. We want to

**generalize the following simple statement to our setting:**

Proposition 5.5. Let G be a graph, W ⊆ V (G) a set of vertices, A, B ⊆ W two disjoint subsets, and an (A, B)-separator S. If |S| |A|, |B|, then |(C ∩ W ) ∪ S| |W | for every component C of G \ S.

The proof of Prop. 5.5 is easy to see: every component C of G \ S is disjoint from either A or B, thus |C ∩ W | is at most |W | − min{|A|, |B|} |W | − |S|, implying that |(C ∩ W ) ∪ S| is less than |W |. Statements of this form are useful when constructing tree decompositions in a recursive way. In our setting, we want to measure the size of the sets using the function b∗, not by the number of vertices. More precisely, we measure the size of S and (C ∩ W ) ∪ S using b∗, while the size of W, A, and B are measured using the fractional independent set

**µ deﬁned by Lemma 5.3. The reason for this will be apparent in the proof of Lemma 5.10:**

we want to claim that if such a separator S does not exist for any A, B ⊆ W, then W is a (µ, λ)-connected set for this fractional independent set µ.

** Lemma 5.6.**

Let H be a hypergraph, let b be an edge-dominated monotone submodular function deﬁned on V (H) with b(∅) = 0 and let W be a set of vertices. Let πW be an ordering of V (H), and let µ(v) := ∂bπW,W (v) for v ∈ W and µ(v) = 0 otherwise. Let A, B ⊆ W be two disjoint sets, and let S be an (A, B)-separator. If b∗ (S) µ(A), µ(B), then b∗ ((C ∩ W ) ∪ S) µ(W ) for every component C of H \ S.

Proof. Let C be a component of H \ S and let Z := (C ∩ W ) ∪ S. Let πS be the ordering reaching the minimum in the deﬁnition of b∗ (S). Let us deﬁne the ordering π that starts with S in the order of πS, followed by C ∩ W in the order of πW, and ﬁnished by

b∗ (Z) ≤ bπ (Z) = ∂bπ,Z (v) ≤ b∗ (S) + µ(C ∩ W ) ∂bπ,Z (v) + v∈S v∈C∩W µ(A) + µ(W \ A) = µ(W ).

5.2. Submodular separation This section is devoted to understanding what fractional separation means: we show that having a small fractional (A, B)-separator is essentially equivalent to the property that for every edge-dominated submodular function b, there is an (A, B)-separator S such that b(S) is small. The proof is based on a standard trick that is often used for rounding fractional solutions for separation problems: we deﬁne a distance function and show by an averaging argument that cutting at some distance t gives a small separator. However, in our setting, we need signiﬁcant new ideas to make this trick work: the main diﬃculty is that the cost function b is deﬁned on subsets of vertices and is not a modular function deﬁned by the cost of vertices. To overcome this problem, we use the deﬁnitions in Section 5.1 (in particular, the function ∂bπ (v)) to assign a cost to every single vertex.

**Theorem 5.7. Let H be a hypergraph, X, Y ⊆ V (H) two sets of vertices, and b :**

V (H) → R+ an edge-dominated monotone submodular function with b(∅) = 0. Suppose that s is a fractional (X, Y )-separator of weight at most w. Then there is an (X, Y )-separator S ⊆ V (H) with b(S) ≤ b∗ (S) = O(w).

Proof. The total weight of the edges covering a vertex v is e∈E(H),v∈e s(e); let us deﬁne x(v) := min{1, e∈E(H),v∈e s(e)}. It is clear that if P is a path from X to Y, then v∈P x(v) ≥ 1. We deﬁne the distance d(v) to be the minimum of v ∈P x(v ), taken over all paths from X to v (this means that d(v) = x(v) for every v ∈ X, that is, d(v) 0 is possible for v ∈ X). It is clear that d(v) ≥ 1 for every v ∈ Y. Let us associate the closed interval ι(v) = [d(v) − x(v), d(v)] to each vertex v. If v is in X, then the left endpoint of ι(v) is 0, while if v is in Y, then the right endpoint of ι(v) is at least 1.

Let u and v be two adjacent vertices in H such that d(u) ≤ d(v). It is easy to see that d(v) ≤ d(u) + x(u): there is a path P from X to u such that u ∈P x(u ) = d(u), thus the path P obtained by appending v to P has v ∈P x(v ) = u ∈P x(u )+x(v) = d(u)+x(v).

**Therefore, we have:**

** Claim 1. If u and v are adjacent, then ι(u) ∩ ι(v) = ∅.**

The class of a vertex v ∈ V (H) is the largest integer κ(v) such that x(v) ≤ 2−κ(v), and we deﬁne κ(v) := ∞ if x(v) = 0. Recall that x(v) ≤ 1, thus κ(v) is nonnegative. The oﬀset of a vertex v is the unique value 0 ≤ α 2 · 2−κ(v) such that d(v) = i(2 · 2−κ(v) ) + α for some integer i. In other words, if the class is 0, 1, 2,..., the oﬀset is d(v) modulo 2, 1, 1/2,..., respectively. Let us deﬁne an ordering π = (v1,..., vn ) of V (H) such that — κ(v) is nondecreasing, — among vertices having the same class, the oﬀset is nondecreasing.