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

On the complexity side, ﬁxed-parameter tractability of CSP(H) seems to be a more robust question than polynomial-time solvability. For example, any polynomial-time reduction to CSP(H) should be able to pick a member of H, thus it seems that polynomial-time reduction to CSP(H) is only possible if certain artiﬁcial technical conditions are imposed on H (such as there is an algorithm eﬃciently generating appropriate members of H). Furthermore, there are classes H for which CSP(H) is polynomial-time equivalent to Log Clique [Grohe 2007], thus we cannot hope to classify CSP(H) into polynomial-time solvable and NP-hard cases.

Another diﬃculty in understanding polynomial-time solvability is that it can depend on the “irrelevant” parts of the hypergraph. Suppose for example that there is class H for which CSP(H) is not polynomial-time solvable, but it is ﬁxed-parameter tractable: it can be solved in time f (H) · ( I )O(1). Let H be constructed the following way: for every H ∈ H, class H contains a hypergraph H that is obtained from H by adding a new component that is a path of length f (H). This new path is trivial with respect to the CSP problem, thus any algorithm for CSP(H) can be used for CSP(H ) as well. Consider an instance I of CSP(H ) having hypergraph H, which was obtained from hypergraph H. After taking care of the path, the assumed algorithm for CSP(H) can solve this instance in time f (H) · ( I )O(1), which is polynomial in I : instance I contains a representation of H, which has at least f (H) vertices, thus I is at least f (H). Therefore, CSP(H ) is polynomial-time solvable.

This example shows that aiming for polynomial-time solvability instead of ﬁxed-parameter tractability might require understanding such subtle, but mostly irrelevant phenomena.

In the hardness results obtained so far, evidence for the non-existence of polynomial-time algorithms is given not in the form of NP-hardness, but by giving evidence that the problem is not even ﬁxed-parameter tractable. In Theorem 1.1, it is a remarkable coincidence that polynomial-time solvability and ﬁxed-parameter tractability are equivalent. However, there is no reason to expect this to remain true in more general cases. Therefore, as discussed above, it makes sense to focus ﬁrst on understanding the ﬁxed-parameter tractability of the problem.

Organization. For convenience, Section 2 collects many of the deﬁnitions appearing in the paper. The reader might want to skim through this at ﬁrst and refer to appropriate parts of it later. Submodular width and other width measures are deﬁned in Section 3.

Section 4 contains the algorithmic part of the paper: the algorithm for classes with bounded submodular width. Section 5 characterizes large submodular width with highly connected sets, while Section 6 uses highly connected sets to ﬁnd good embeddings in hypergraph.

The main hardness result of the paper is proved in Section 7.

2. PRELIMINARIES Constraint satisfaction problems. We brieﬂy recall the most important notions related to CSP. For more background, see e.g., [Grohe 2006; Feder and Vardi 1999].

Definition 2.1. An instance of a constraint satisfaction problem is a triple (V, D, C),

**where:**

— V is a set of variables, — D is a domain of values, — C is a set of constraints, {c1, c2,..., cq }. Each constraint ci ∈ C is a pair si, Ri,

**where:**

— si is a tuple of variables of length mi, called the constraint scope, and — Ri is an mi -ary relation over D, called the constraint relation.

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

**Tractable hypergraph properties for constraint satisfaction and conjunctive queries A:9**

For each constraint si, Ri the tuples of Ri indicate the allowed combinations of simultaneous values for the variables in si. The length mi of the tuple si is called the arity of the constraint. A solution to a constraint satisfaction problem instance is a function f from the set of variables V to the domain of values D such that for each constraint si, Ri with si = vi1, vi2,..., vim, the tuple f (vi1 ), f (vi2 ),..., f (vim ) is a member of Ri. We say that an instance is binary if each constraint relation is binary, i.e., mi = 2 for each constraint. 4 It can be assumed that the instance does not contain two constraints si, Ri, sj, Rj with si = sj, since in this case the two constraints can be replaced by the constraint si, Ri ∩ Rj.

In the input, the relation appearing in a constraint is represented by listing all the tuples of the constraint. We denote by I the size of the representation of the instance I = (V, D, C).

It can be assumed that |D| ≤ I : elements of D that do not appear in any relation can be safely removed.

Let I = (V, D, C) be a CSP instance and let V ⊆ V be a nonempty subset of variables. If f is a solution of I, then prV f is the projection of f to V, which is simply the restriction of the function f : V → D to V ⊆ V. If R is a set of solutions for I, then we let prV R = {prV f | f ∈ R}.

The projection prV I of I to V is a CSP I = (V, D, C ), where C is deﬁned the following way: For each constraint c = (v1,..., vk ), R having at least one variable in V, there is a corresponding constraint c in C. Suppose that vi1,..., vi are the variables among v1,..., vk that are in V. Then the constraint c is deﬁned as (vi1,..., vi ), R, where the relation R is the projection of R to the coordinates i1,..., i, that is, R contains an tuple (d1,..., d ) ∈ D if and only if there is a k-tuple (d1,..., dk ) ∈ R such that dj = dij for 1 ≤ j ≤. Clearly, if f is a solution of I, then prV f is a solution of prV I (but the converse is not true). For a subset V ⊆ V, we denote by solI (V ) the set of all solutions of prV I (which can contain a solution which is not the projection of any solution of I). If the instance I is clear from the context, we drop the subscript.

The primal graph (or Gaifman graph) of a CSP instance I = (V, D, C) is a graph with vertex set V such that u, v ∈ V are adjacent if and only if there is a constraint whose scope contains both u and v. The hypergraph of a CSP instance I = (V, D, C) is a hypergraph H with vertex set V, where e ⊆ V is an edge of H if and only if there is a constraint whose scope is e (more precisely, where the scope is an |e|-tuple s, whose coordinates form a permutation of the elements of e). For a class H of graphs, we denote by CSP(H) the problem restricted to instances whose hypergraph is in H.

Graphs and hypergraphs. If G is a graph or hypergraph, then we denote by V (G) and E(G) the set of vertices and the set of edges of G, respectively. Vertices u, v ∈ V (G) are adjacent if there is an edge e ∈ E(G) with u, v ∈ e. A set K ⊆ V (G) is a clique if the vertices in K are pairwise adjacent. If H is a hypergraph and V ⊆ V (H), then the subhypergraph induced by V is a hypergraph H with vertex set S and ∅ ⊂ e ⊆ V is an edge of H if and only if there is an edge e ∈ E(H) with e ∩ V = e. We denote by H \ S the subhypergraph of H induced by V (H) \ S.

Paths, separators, and ﬂows in hypergraphs. A path P in hypergraph H is an ordered sequence v0, v1,..., vr of distinct vertices such that vi and vi−1 are adjacent for every 1 ≤ i r. We distinguish the endpoints of a path: vertex v0 is the ﬁrst endpoint of P and vr is the second endpoint of P. For a path of length zero, the ﬁrst and second endpoints coincide. A path is an X − Y path if its ﬁrst endpoint is in X and its second endpoint is in Y. A path P = v1 v2... vt is minimal if there are no shortcuts, i.e., vi and vj are not adjacent if |i − j| 1. Note that a minimal path intersects each edge at most twice.

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

An (X, Y )-separator is a set S ⊆ V (H) of vertices such that there is no (X \ S) − (Y \ S) 4 Itis unfortunate that while some communities use the term “binary CSP” in the sense that each constraint is binary (as does this paper), others use it in the sense that the variables are 0-1, i.e, the domain size is 2.

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

A:10 D. Marx path in H \ S, or in other words, every X − Y path of H contains at least one vertex of S.

In particular, this means that X ∩ Y ⊆ S.

An assignment s : E(H) → R+ is a fractional (X, Y )-separator if every X − Y path P is covered by s, that is, e∈E(H),e∩P =∅ s(e) ≥ 1. The weight of the fractional separator s is e∈E(H) s(e).

Let H be a hypergraph and let P be the set of all paths in H. A ﬂow of H is an assignment f : P → R+ such that P ∈P,P ∩e=∅ f (P ) ≤ 1 for every e ∈ E(H). The value of the ﬂow f is P ∈P f (P ). We say that a path P appears in ﬂow f, or simply P is a path of f if f (P ) 0. For some X, Y ⊆ V (H), an (X, Y )-ﬂow is a ﬂow f such that only X − Y paths appear in f. A standard LP duality argument shows that the minimum weight of a fractional (X, Y )-separator is equal to the maximum value of an (X, Y )-ﬂow.

If f, f are ﬂows such that f (P ) ≤ f (P ) for every path P, then f is a subﬂow of f. The r sum of the ﬂows f1,..., fr is a mapping that assigns weight i=1 fi (P ) to each path P.

Note that the sum of ﬂows is not necessarily a ﬂow itself as the total weight of the paths intersecting a certain edge can be more than 1 in the sum. If the sum of f1,..., fr happens to be a ﬂow, then we say that f1,..., fr are compatible.

Highly connected sets. An important step in understanding various width measures is showing that if the measure is large, then the (hyper)graph contains a highly connected set (in a certain sense). We deﬁne here the notion of highly connectedness that will be used in the paper. First, recall that a fractional independent set of a hypergraph H is a mapping µ : V (H) → [0, 1] such that v∈e µ(v) ≤ 1 for every e ∈ E(H). We extend functions on the vertices of H to subsets of vertices of H the natural way by setting µ(X) := v∈X µ(v), thus we can equivalently say that µ : V (H) → [0, 1] is a fractional independent set if and only if µ(e) ≤ 1 for every e ∈ E(H).

Let µ be a fractional independent set of hypergraph H and let λ 0 be a constant. We say that a set W ⊆ V (H) is (µ, λ)-connected if for any two disjoint sets A, B ⊆ W, the minimum weight of a fractional (A, B)-separator is at least λ · min{µ(A), µ(B)}. Note that if W is (µ, λ)-connected, then W is (µ, λ )-connected for every λ λ and every W ⊆ W is also (µ, λ)-connected. Informally, if W is (µ, λ)-lambda connected for some fractional independent set µ such that µ(W ) is “large”, then we call W a highly connected set. For λ 0, we denote by conλ (H) the maximum of µ(W ), taken over every fractional independent set µ and (µ, λ)-connected set W of H. Note that if λ ≤ λ, then conλ (H) ≥ conλ (H).

Throughout the paper, λ can be thought of as a suﬃciently small universal constant, say, 0.001.

Embeddings. The hardness result presented in the paper and earlier hardness results for CSP(H) [Grohe 2007; Marx 2011; 2010b] are based on embedding some other problem (with a certain graph structure) in a CSP instance whose hypergraph is a member of H. Thus we need appropriate notions of embedding a graph in a (hyper)graph. Let us ﬁrst recall the deﬁnition of minors in graphs. A graph F is a minor of G if F can be obtained from G by a sequence of vertex deletions, edge deletions, and edge contractions. The following alternative deﬁnition is more relevant from the viewpoint of embeddings: a graph F is a minor of G if there is a mapping ψ that maps each vertex of F to a connected subset of V (G) such that ψ(u) ∩ ψ(v) = ∅ for u = v, and if u, v ∈ V (F ) are adjacent in F, then there is an edge in E(G) connecting ψ(u) and ψ(v).

A crucial diﬀerence between the proof of Theorem 1.1 in [Grohe 2007] and the proof of Theorem 1.2 in [Marx 2010b] is that the former result is a based on ﬁnding a minor embedding of a grid, while the latter result uses a more general notion of embedding where the images of distinct vertices are not necessarily disjoint, but can overlap in a controlled way. We deﬁne such embeddings the following way. We say that two sets of vertices X, Y ⊆ V (H) touch if either X ∩ Y = ∅, or there is an edge e ∈ E(H) intersecting both X and Y.

An embedding of graph G into hypergraph H is a mapping ψ that maps each vertex of G Journal of the ACM, Vol. V, No. N, Article A, Publication date: January YYYY.

Tractable hypergraph properties for constraint satisfaction and conjunctive queries A:11 to a connected subset of V (H) such that if u and v are adjacent in G, then ψ(u) and ψ(v) touch. The depth of a vertex v ∈ V (H) in embedding ψ is dψ (v) := |{u ∈ V (G) | v ∈ ψ(u)}|, the number of vertices of G whose images contain v. The vertex depth of the embedding is maxv∈V (H) dψ (v). Observe that ψ is a minor mapping if and only if it has vertex depth