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

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

A:40 D. Marx To bound the edge depth of the embedding φ, consider an edge e. The total weight of the paths intersecting e is at most 1 and a path with weight w is used in the image of at most 2(q/ ) · w vertices. Each path intersects e in at most 2 vertices (as we can assume that the paths appearing in the ﬂows are minimal), thus a path with weight w contributes at most 4(q/ ) · w to the depth of e. Thus the edge depth of φ is at most √ 3 1 4(q/ ) = O(m/(λ k)) = O(m/(λ 2 conλ (H) 4 )).

6.3. Connection with adaptive width As an easy consequence of the embedding result Corollary 6.2, we can show that large

**submodular width implies large adaptive width:**

** Lemma 6.9.**

For every hypergraph H, adw(H) = Ω(emb(H)).

Proof. Suppose that emb(H) α. This means that there is an integer mα such that every graph with m ≥ mα edges has an embedding into H with edge depth m/α. It is wellknown that there are arbitrarily large sparse graphs whose treewidth is linear in the number of vertices (for example, bounded-degree expanders, see e.g., [Grohe and Marx 2009]): for some universal constant β, there is a graph G with m ≥ mα edges and treewidth at least βm. Thus there is an embedding φ from G to H with edge depth at most q ≤ m/α. Let d(v) be the depth of vertex v in the embedding and let us deﬁne µ(v) := d(v)/q. From the deﬁnition of edge depth, it is clear that µ is a fractional independent set. Suppose that there is a tree decomposition (T, Bv∈V (T ) ) of H having µ-width w. This tree decomposition can be turned into a tree decomposition (T, Bv∈V (T ) ) of G: for every Bt ⊆ V (H), let Bt := {u ∈ V (G) | φ(u) ∩ Bt = ∅} contain those vertices of G whose images intersect Bt.

Now µ(Bt ) ≤ w means that v∈Bt d(v) ≤ qw, which implies that |Bt | ≤ qw. Thus the width of (T, Bv∈V (T ) ) is less than qw, which means that w has to be at least βm/q = Ω(α), the required lower bound on the adaptive width of H.

**Combining Theorem 5.1 and Lemma 6.9 gives:**

Corollary 6.10. For every hypergraph H, subw(H) = O(adw(H)4 ).

## 7. FROM EMBEDDINGS TO HARDNESS OF CSP

**We prove the main hardness result of the paper in this section:**

** Theorem 7.1.**

Let H be a recursively enumerable class of hypergraphs with unbounded submodular width. If there is an algorithm A and a function f such that A solves every 1/4 instance I of CSP(H) with hypergraph H ∈ H in time f (H) · I o(subw(H) ), then the Exponential Time Hypothesis fails.

In particular, Theorem 7.1 implies that CSP(H) for such a H is not ﬁxed-parameter

**tractable:**

Corollary 7.2. If H is a recursively enumerable class of hypergraphs with unbounded submodular width, then CSP(H) is not ﬁxed-parameter tractable, unless the Exponential Time Hypothesis fails.

The Exponential Time Hypothesis (ETH) states that there is no 2o(n) time algorithm for n-variable 3SAT. The Sparsiﬁcation Lemma of Impagliazzo et al. [2001] shows that ETH is equivalent to the assumption that there is no algorithm for 3SAT whose running time is subexponential in the number of clauses. This result will be crucial for our hardness proof, as our reduction from 3SAT is sensitive to the number of clauses.

** Theorem 7.3 (Impagliazzo et al.**

[2001]). If there is a 2o(m) time algorithm for mclause 3SAT, then there is a 2o(n) time algorithm for n-variable 3SAT.

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

Tractable hypergraph properties for constraint satisfaction and conjunctive queries A:41 To prove Theorem 7.1, we show that a subexponential-time algorithm for 3SAT exists if CSP(H) can be solved “too fast” for some H with unbounded submodular width. We use the characterization of submodular width from Section 5 and the embedding results of Section 6 to reduce 3SAT to CSP(H) by embedding the incidence graph of a 3SAT formula into a hypergraph H ∈ H. The basic idea of the proof is that if the 3SAT formula has m clauses and the edge depth of the embedding is m/r, then we can gain a factor r in the exponent of the running time. If submodular width is unbounded in H, then we can make this gap r between the number of clauses and the edge depth arbitrary large, and hence the exponent can be arbitrarily smaller than the number of clauses, i.e., the algorithm is subexponential in the number of clauses.

The following simple lemma from [Marx 2010b] gives a transformation that turns a 3SAT instance into a binary CSP instance. We include the proof for completeness.

** Lemma 7.4.**

Given an instance of 3SAT with n variables and m clauses, it is possible to construct in polynomial time an equivalent CSP instance with n + m variables, 3m binary constraints, and domain size 3.

Proof. Let φ be a 3SAT formula with n variables and m clauses. We construct an instance of CSP as follows. The CSP instance contains a variable xi (1 ≤ i ≤ n) corresponding to the i-th variable of φ and a variable yj (1 ≤ j ≤ m) corresponding to the j-th clause of φ. Let D = {1, 2, 3} be the domain. We try to describe a satisfying assignment of φ with these n + m variables. The intended meaning of the variables is the following. If the value of variable xi is 1 (resp., 2), then this represents that the i-th variable of φ is true (resp., false). If the value of variable yj is, then this represents that the j-th clause of φ is satisﬁed by its -th literal. To ensure consistency, we add 3m constraints. Let 1 ≤ j ≤ m and 1 ≤ ≤ 3, and assume that the -th literal of the j-th clause is a positive occurrence of the i-th variable. In this case, we add the binary constraint (xi = 1 ∨ yj = ): either xi is true or some other literal satisﬁes the clause. Similarly, if the -th literal of the j-th clause is a negated occurrence of the i-th variable, then we add the binary constraint (xi = 2 ∨ yj = ).

It is easy to verify that if φ is satisﬁable, then we can assign values to the variables of the CSP instance such that every constraint is satisﬁed, and conversely, if the CSP instance has a solution, then φ is satisﬁable.

Next we show that an embedding from graph G to hypergraph H can be used to simulate a binary CSP instance I1 having primal graph G by a CSP instance I2 whose hypergraph is H. The domain size and the size of the constraint relations of I2 can grow very large in this transformation: the edge depth of the embedding determines how large this increase is.

** Lemma 7.5.**

Let I1 = (V1, D1, C1 ) be a binary CSP instance with primal graph G and let φ be an embedding of G into a hypergraph H with edge depth q. Given I1, H, and the embedding φ, it is possible to construct (in time polynomial in the size of the output) an equivalent CSP instance I2 = (V2, D2, C2 ) with hypergraph H where the size of every constraint relation is at most |D1 |q.

Proof. For every v ∈ V (H), let Uv := {u ∈ V (G) | v ∈ φ(u)} be the set of vertices in G whose images contain v, and for every e ∈ E(H), let Ue := v∈e Uv. Observe that for every e ∈ E(H), we have |Ue | ≤ v∈e |Uv | ≤ q, since the edge depth of φ is q. Let D2 be the set of integers between 1 and |D1 |q. For every v ∈ V (H), the number of assignments from Uv to D1 is clearly |D1 ||Uv | ≤ |D1 |q. Let us ﬁx a bijection hv between these assignments on Uv and the set {1,..., |D1 ||Uv | } ⊆ D2.

The set C2 of constraints of I2 are constructed as follows. For each e ∈ E(H), there is a constraint se, Re in C2, where se is an |e|-tuple containing an arbitrary ordering of the elements of e. The relation Re is deﬁned the following way. Suppose that vi is

where the last inequality follows from the fact that φ has edge depth at most q.

To prove that I1 and I2 are equivalent, assume ﬁrst that I1 has a solution f1 : V1 → D1.

For every v ∈ V2, let us deﬁne f2 (v) := hv (prUv f2 ), that is, the integer between 1 and |D1 ||Uv | corresponding to the projection of assignment f2 to Uv. It is easy to see that f2 is a solution of I2.

Assume now that I2 has a solution f2 : V2 → D2. For every v ∈ V (H), let fv := h−1 (f2 (v)) v be the assignment from Uv to D1 that corresponds to f2 (v) (note that by construction, f2 (v) is at most |D1 ||Uv |, hence h−1 (f2 (v)) is well-deﬁned). We claim that these assignments are v compatible: if u ∈ Uv ∩ Uv for some u ∈ V (G) and v, v ∈ V (H), then fv (u) = fv (u).

Recall that φ(u) is a connected set in H, hence there is a path between v and v in φ(u).

We prove the claim by induction on the distance between v and v in φ(u). If the distance is 0, that is, v = v, then the statement is trivial. Suppose now that the distance of v and v is d 0. This means that v has a neighbor z ∈ φ(u) such that the distance of z and v is d − 1. Therefore, fz (u) = fv (u) by the induction hypothesis. Since v and z are adjacent in H, there is an edge E ∈ E(H) containing both v and z. From the way I2 is deﬁned, this means that fv and fz are compatible and fv (u) = fz (u) = fv (u) follows, proving the claim. Thus the assignments {fv | v ∈ V (H)} are compatible and these assignments together deﬁne an assignment f1 : V (G) → D. We claim that f1 is a solution of I1. Let c = (u1, u2 ), R be an arbitrary constraint of I1. Since u1 u2 ∈ E(G), sets φ(u1 ) and φ(u2 ) touch, thus there is an edge e ∈ E(H) that contains a vertex v1 ∈ φ(u1 ) and a vertex v2 ∈ φ(u2 ) (or, in other words, u1 ∈ Uv1 and u2 ∈ Uv2 ). The deﬁnition of ce in I2 ensures that f1 restricted to Uv1 ∪ Uv2 satisﬁes every constraint of I1 whose scope is contained in Uv1 ∪ Uv2 ; in particular, f1 satisﬁes constraint c.

Now we are ready to prove Theorem 7.1, the main result of the section. We show that if there is a class H of hypergraphs with unbounded submodular width such that CSP(H) is FPT, then this algorithm can be used to solve 3SAT in subexponential time. The main ingredients are the embedding result of Theorem 6.1, and Lemmas 7.4 and 7.5 above on reduction to CSP. Furthermore, we need a way of choosing an appropriate hypergraph from the set H. As discussed earlier, the larger the submodular width of the hypergraph is, the more we gain in the running time. However, we should not spend too much time on constructing the hypergraph and on ﬁnding an embedding. Therefore, we use the same technique as in [Marx 2010b]: we enumerate a certain number of hypergraphs and we try all of them simultaneously. The number of hypergraphs enumerated depends on the size of the 3SAT instance. This will be done in such a way that guarantees that we do not spend

= f2 (H, λ) · mO(1) · 3cλ m/ι(k) for an appropriate function f2 (H, λ) depending only on H and λ.

Algorithm B for 3SAT proceeds as follows. Let us ﬁx an arbitrary computable enumeration H1, H2,... of the hypergraphs in H. Given an m-clause 3SAT formula I, algorithm B spends the ﬁrst m steps on enumerating these hypergraphs; let H be the last hypergraph produced by this enumeration (we assume that m is suﬃciently large that ≥ 1). Next we start simulating the algorithms A[I, H1 ], A[I, H2 ],..., A[I, H ] in parallel. When one of the simulations stops and returns an answer, then we stop all the simulations and return the answer. It is clear that algorithm B will correctly decide the satisﬁability of I.

We claim that there is a universal constant d such that for every s, there is an ms such that for every m ms, the running time of B is at most (m · 2m/s )d on an m-clause formula.

Clearly, this means that the running time of B is 2o(m).

For any positive integer s, let ks be the smallest positive integer such that ι(ks ) ≥ s (as ι is unbounded, this is well deﬁned). Let is be the smallest positive integer such that subw(His ) ≥ ks (as H has unbounded submodular width, this is also well deﬁned). Set ms suﬃciently large that ms ≥ f2 (His, λ) and the ﬁxed enumeration of H reaches His in less then ms steps. This means that if we run B on a 3SAT formula I with m ≥ ms clauses, then ≥ is and hence A[I, His ] will be one of the simulations started by B. The simulation of A[I, His ] terminates in f2 (His, λ)mO(1) · 3cλ m/ι(subw(His )) ≤ m · mO(1) · 3cλ m/s steps. Taking into account that we simulate ≤ m algorithms in parallel and all the simulations are stopped not later than the termination of A[I, His ], the running time of B can Journal of the ACM, Vol. V, No. N, Article A, Publication date: January YYYY.

A:44 D. Marx be bounded polynomially by the running time of A[I, His ]. Therefore, there is a constant d such that the running time of B is at most (m · 2m/s )d, as required.

** Remark 7.6.**

Recall that if φ is an embedding of G into H, then the depth of an edge e ∈ E(H) is dφ (e) = v∈V (G) |φ(v) ∩ e|. A variant of this deﬁnition would be to deﬁne the depth of e as dφ (e) = |{v ∈ V (G) | φ(v)∩e = ∅}|, i.e., if φ(v) intersects e, then v contributes only 1 to the depth of e, not |φ(v) ∩ e| as in the original deﬁnition. Let us call this variant weak edge depth, it is clear that the weak edge depth of an embedding is at most the edge depth of the embedding.

** Lemma 7.5 can be made stronger by requiring only that the weak edge depth is at most q.**

Indeed, the only place where we use the bound on edge depth is in Inequality (4). However, the size of the relation Re can be bounded by the number of possible assignments on Ue in instance I1. If weak edge depth is at most q, then |Ue | ≤ q, and the |D1 |q bound on the size of Re follows.

** Remark 7.7.**