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

1. Because in our case we want to control the size of the constraint relations, we need a notion of depth that is sensitive to “what the edges see.” We deﬁne the depth dψ (e) of an edge e ∈ E(H) as dψ (e) = v∈e dψ (e) and the edge depth to be the maximum of e taken over all edges e ∈ E(H). Equivalently, we can deﬁne the depth of an edge e ∈ H as dψ (e) = v∈V (G) |ψ(v) ∩ e|, that is, each vertex v contributes |ψ(v) ∩ e| to the depth. (A diﬀerent, perhaps more natural, deﬁnition of edge depth would be to deﬁne it simply as a maximum number of sets ψ(v) that intersect an edge. Somewhat unexpectedly, most results of the paper remain true with both notions; see Remarks 7.6–7.7.) Trivially, for any graph G and hypergraph H, there is an embedding of G into H having vertex depth and edge depth at most |V (G)|. If G has m edges and no isolated vertices, then |V (G)| is at most 2m. We are interested in how much we can gain compared to this trivial solution of depth O(m). We deﬁne the embedding power emb(H) to be the maximum (supremum) value of α for which there is an integer mα such that every graph G with m ≥ mα edges has an embedding into H with edge depth m/α. It might look unmotivated that we deﬁne embedding power in terms of the number of edges of G: deﬁning it in terms of the number of vertices might look more natural.

3. WIDTH PARAMETERS Treewidth and its various generalizations are deﬁned in this section. We follow the framework of width functions introduced by Adler [2006]. A tree decomposition of a hypergraph H is a tuple (T, (Bt )t∈V (T ) ), where T is a tree and (Bt )t∈V (T ) is a family of subsets of V (H) satisfying the following two conditions: (1) for each e ∈ E(H) there is a node t ∈ V (T ) such that e ⊆ Bt, and (2) for each v ∈ V (H) the set {t ∈ V (T ) | v ∈ Bt } is connected in T. The sets Bt are called the bags of the decomposition. Let f : 2V (H) → R+ be a function that assigns a nonnegative real number to each nonempty subset of vertices. The f -width of a tree-decomposition (T, (Bt )t∈V (T ) ) is max f (Bt ) | t ∈ V (T )}. The f -width of a hypergraph H is the minimum of the f -widths of all its tree decompositions. In other words, f -width(H) ≤ w if and only if there is a tree decomposition of H where f (B) ≤ w for every bag B.

The main idea of tree decomposition based algorithms is that if we have a tree decomposition for instance I such that at most C assignments on Bt have to be considered for each bag Bt, then the problem can be solved by dynamic programming in time polynomial in C and I. The various width notions try to guarantee the existence of such decompositions.

**The simplest such notion, treewidth, can be deﬁned as follows:**

Definition 3.1. Let s(B) = |B| − 1. The treewidth of H is tw(H) := s-width(H).

Further width notions deﬁned in the literature can also be conveniently deﬁned using this setup. A subset E ⊆ E(H) is an edge cover if e∈E e = V (H). The edge cover number ρ(H) is the size of the smallest edge cover (here we assume that H has no isolated vertices).

For X ⊆ V (H), let ρH (X) be the size of the smallest set of edges covering X.

Definition 3.2. The generalized hypertree width of H is hw(H) := ρH -width(H).

The original (nongeneralized) deﬁnition [Gottlob et al. 2002a] of hypertree width includes an additional requirement on the decomposition (we omit the details), thus it cannot be

**A crucial idea in [Marx 2011] is to make the choice of tree decomposition adaptive:**

instead of assigning a single decomposition to each hypergraph, we choose the best decomposition based on additional properties of the current instance. Motivated by this idea, we generalize the notion of f -width from a single function f to a class of functions F. Let H be a hypergraph and let F be an arbitrary (possibly inﬁnite) class of functions that assign nonnegative real numbers to nonempty subsets of vertices of H. The F-width of H is F-width(H) := sup f -width(H) | f ∈ F. Thus if F-width(H) ≤ k, then for every f ∈ F, hypergraph H has a tree decomposition with f -width at most k. Note that this tree decomposition can be diﬀerent for the diﬀerent functions f. For normalization purposes, we consider only functions f on V (H) that satisfy f (∅) = 0 and that are edge-dominated, that is, f (e) ≤ 1 holds for every e ∈ E(H).

Using these deﬁnitions, we can deﬁne adaptive width, introduced in [Marx 2011], as follows. Recall that in Section 2, we stated that if µ is a fractional independent set, then µ is extended to subsets of vertices by deﬁning µ(X) := v∈X µ(v) for every X ⊆ V (H).

Definition 3.4. The adaptive width adw(H) of a hypergraph H is F-width(H), where F is the set of all fractional independent sets of H.

A function f : 2V (H) → R is modular if f (X) = v∈X cv for some constants cv (v ∈ V (H)).

The function µ(X) arising from a fractional independent set is clearly a modular and edge dominated function, in fact, in Deﬁnition 3.4 we can equivalently deﬁne F as the set of all nonnegative modular edge-dominated functions on V (H). The main new deﬁnition of the paper is a new width measure, which is obtained by imposing a requirement weaker than

**modularity on the functions in F (hence the considered set F of functions is larger):**

Definition 3.5. A function b : 2V (H) → R+ is submodular if b(X) + b(Y ) ≥ b(X ∩ Y ) + b(X ∪ Y ) holds for every X, Y ⊆ V (H). Given a hypergraph H, let F contain every edge-dominated monotone submodular function b on V (H) with b(∅) = 0. The submodular width of hypergraph H is subw(H) := F-width(H).

It is well-known that submodular functions can be equivalently characterized by the property that b(X ∪ v) − b(X), the marginal value of v with respect to X, is a nonincreasing function of X. That is, for every v and X ⊆ Y, b(X ∪ v) − b(X) ≥ b(Y ∪ v) − b(Y ). (1) It is clear that subw(H) ≥ adw(H): Deﬁnition 3.5 considers a larger set of functions than Deﬁnition 3.4. Furthermore, we show that subw(H) is at most the fractional hypertree width fhw(H). This is a straightforward consequence of the fact that an edge-dominated

**submodular function is always bounded by the fractional cover number:**

** Lemma 3.6.**

Let H be a hypergraph and b be a monotone edge-dominated submodular function with b(∅) = 0. Then b(S) ≤ ρ∗ (S) for every S ⊆ V (H).

H

(the equality is a simple telescopic sum; the inequality uses (1), i.e., the marginal value of vi with respect to Vi−1 is not greater than with respect to e ∩ Vi−1 ).

(in the ﬁrst inequality, we use that f is edge dominated; in the last inequality, we use that γ is a fractional edge cover).

Proposition 3.7. For every hypergraph H, subw(H) ≤ fhw(H).

Proof. Let (T, Bt∈V (T ) ) be a tree decomposition of H whose ρ∗ -width is fhw(H). If b is H an edge-bounded monotone submodular function with b(∅) = 0, then by Lemma 3.6, b(Bt ) ≤ ρ∗ (Bt ) ≤ fhw(H) for every bag Bt of the decomposition, i.e., b-width(H) ≤ fhw(H). This H is true for every such function b, hence subw(H) ≤ fhw(H).

Since adw(H) ≤ subw(H) ≤ fhw(H), if a class H of hypergraphs has bounded fractional hypertree width, then it has bounded submodular width, and if a class H has bounded submodular width, then it has bounded adaptive width. Surprisingly, it turns out that the latter implication is actually an equivalence: Corollary 6.10 shows that subw(H) is at most O(adw(H)4 ), thus a class of hypergraphs has bounded submodular width if and only if it has bounded adaptive width. In other words, large submodular width can be certiﬁed already by modular functions: if submodular width is unbounded in H and we want to choose an H ∈ H and a submodular function b such that the b-width of H is larger than some constant k, then we can choose H and b such that b is actually modular. There is no intuitive reason why this is true: submodular functions seem to be much more powerful than modular functions. Still, we obtain this result as a byproduct of our characterization of submodular width.

There is no such connection between adaptive width and fractional hypertree width: it is shown in [Marx 2011] that there is a class of hypergraphs with bounded adaptive width and unbounded fractional hypertree width. Thus the property bounded fractional hypertree width is a strictly weaker property than bounded adaptive/submodular width.

Figure 2 shows the relations of the hypergraph properties deﬁned in this section (note that the elements of this Venn diagram are sets of hypergraphs; e.g., the set “bounded treewidth” contains every set H of hypergraphs with bounded treewidth). As discussed above, all the inclusions in the ﬁgure are proper.

Finally, let us remark that there have been investigations of tree decompositions and branch decompositions of submodular functions and matroids in the literature [Hlinˇn´ ey and Oum 2008; Oum and Seymour 2007; Hlinˇn´ and Whittle 2006; Hlinˇn´ 2005; Amini ey ey

**et al. 2009]. However, in those results the submodular function is a connectivity function:**

b(S) describes the boundary of S, that is, the cost of separating S from its complement. In

Fig. 2. Hypergraph properties that make CSP ﬁxed-parameter tractable.

our case, b(S) describes the cost of the separator S itself. Therefore, we are in a completely diﬀerent setting and the previous results cannot be used.

## 4. FROM CSP INSTANCES TO SUBMODULAR FUNCTIONS

In this section, we prove the main algorithmic result of the paper: CSP(H) is ﬁxed-parameter tractable if H has bounded submodular width.** Theorem 4.1.**

Let H be a class of hypergraphs such that subw(H) ≤ c0 for every O(|V (H)|) H ∈ H. Then CSP(H) can be solved in time 2c0 ·2 · I O(c0 ).

**The proof of Theorem 4.1 is based on two main ideas:**

(1) A CSP instance I can be decomposed into a bounded number of “uniform” CSP instances I1,..., It (Lemma 4.11). Here uniform means that if B ⊆ A are two sets of variables, then every solution of prB Ij has roughly the same number of extensions to prA Ij.

(2) If I is a uniform CSP instance, then (the logarithm of) the number of solutions on the diﬀerent projections of I can be described by an edge-dominated monotone submodular function b (Lemma 4.12). Therefore, if the hypergraph H of I has bounded submodular width, then it follows that there is a tree decomposition where every bag has a polynomially bounded number of solutions. This means that the existence of a solution can be tested by standard techniques.

While our algorithm is based on these two ideas, the technical implementation is slightly diﬀerent. First, we can achieve uniformity only on “small sets” of variables. For technical reasons, we have to ensure a certain consistency condition (for example, in order to ensure that the submodular function b is monotone). It follows from the consistency condition that when we ﬁnd a tree decomposition for a uniform instance such that every bag has a small number of solutions, then this automatically implies that the instance has a solution; we do not even have to use the tree decomposition (see Lemma 4.7).

In Section 4.1 we deﬁne the notion of consistency that we use and discuss how it can be achieved. Section 4.2 describes how the instance can be partitioned into uniform instances.

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

Tractable hypergraph properties for constraint satisfaction and conjunctive queries A:15 Section 4.3 shows how a submodular function can be deﬁned based on a uniform instance, connecting our algorithm to submodular width.

4.1. Consistency Recall from Section 2 that prA I is instance I projected to a set A of variables and solI (A) is the set of all solutions of prA I. Note that, in general, it is possible that | solI (S )| | solI (S)| for some S ⊂ S. In the implementation of the ﬁrst idea (Lemma 4.11), we guarantee uniformity only to subsets of variables that are “small” in the following hereditary sense Definition 4.2. Let I be a CSP instance and M ≥ 1 an integer. We say that S ⊆ V is M -small if | solI (S )| ≤ M for every S ⊆ S.

It is not diﬃcult to ﬁnd all the M -small sets, and every solution of the instances projected

**onto these sets:**

** Lemma 4.3.**

Let I = (V, D, C) be a CSP instance and M ≥ 1 an integer. There is an algorithm with running time 2O(|V |) · poly( I, M ) that ﬁnds the set S of all M -small sets S ⊆ V and constructs solI (S) for each such S ∈ S.

Proof. For i = 1, 2,..., |V |, we ﬁnd every M -small set S of size i and construct solI (S).

This is trivial to do for i = 1. Suppose that we have already found the collection Si of all M -small sets of size exactly i. By deﬁnition, every size i subset S of an M -small set S of size i + 1 is an M -small set. Thus we can ﬁnd every M -small set of size i + 1 by enumerating every S ∈ Si and checking for every v ∈ V \ S whether S := S ∪ {v} is M -small. To check whether S is M -small, we ﬁrst check whether every subset of size i is M -small, which is easy to do using the set Si. Then we construct solI (S ): this can be done by enumerating every tuple s ∈ solI (S) and every extension of s by a new value from D. Thus we need to consider at most | solI (S)| · |D| ≤ M · |D| tuples as possible members in solI (S ), which means that solI (S ) can be constructed in time polynomial in M and I. If | solI (S )| ≤ M, then we put S into Si+1. As the collection Si contains at most 2|V | sets and every operation is polynomial in M and I, the total running time is 2O(|V |) · poly( I, M ).