A Unified Theory of Structural Tractability for Constraint Satisfaction and Spread Cut Decomposition

1 Introduction

A constraint satisfaction problem consists of a set of variables that must be assigned values subject to certain constraints. These constraints restrict the simultaneous assignments to certain specified subsets of the variables. Many real-world problems can be represented very naturally in this framework [Dechter, 2003; Marriott and Stuckey, 1998]

Similar problems arise in the field of relational databases, where they are referred to as conjunctive query evaluation problems [Kolaitis and Vardi, 2000]. Many of the techniques developed in this paper can also be applied directly to the conjunctive query evaluation problem, but we shall not pursue this application here.

The decision problem for the general constraint satisfaction problem is NP-hard [Mackworth, 1977]. This motivates the search for more restricted subproblems which are tractable, that is, solvable in polynomial-time.

This paper considers subproblems of the constraint satisfaction problem which can be shown to be tractable using socalled structural methods or decomposition methods. These methods rely exclusively on using the structural properties of instances, in other words the way in which the constraints overlap each other.

A variety of such decomposition methods have been developed and applied in both the constraint satisfaction community, and the database community. Examples include methods based on the use of treewidth [Freuder, 1985], cycle cutsets [Dechter and Pearl, 1988], tree-clustering [Dechter and Pearl, 1989], hinges [Gyssens et al., 1994], cycle hypercutsets and hypertrees [Gottlob et al., 2000]. All of these methods rely on reducing a given problem instance to an equivalent instance with a simpler structure, which can then be solved efficiently.

In this paper we present a generic, abstract form of decomposition, which we call a guarded decomposition. We show that all of the earlier decomposition methods can be viewed as special cases of guarded decomposition, each characterized by some simple additional conditions.

One existing decomposition method, based on the use of hypertrees [Gottlob et al., 2000; 2002], is of particular importance as it is has been shown to be strictly more general than many other decomposition methods and that, for each k, it is tractable to to discover hypertree decompositions of width at most k. The general framework presented here allows us to identify a new decomposition method, based on the use of a structure that we call a spread cut. We show that spread-cut decompositions generalize all of the methods previously shown to be generalized by hypertree decompositions, and still it is tractable, for each k to discover spread cut decompositions of width k. Furthermore, we exhibit a family of examples for which the spread-cut decomposition method obtains better decompositions than the hypertree decomposition method.

2 Constraint Satisfaction, Hypergraphs, and Tractability

Definition 2.1 A CSP instance is a triple P = 〈V,D,C〉 where:

• V is a finite set of variables;
• D is a set called the domain of P ;
• C is a set of constraints. Each constraint c ∈ C is a pair c = 〈χ, ρ〉 where χ ⊆ V is a set of variables, called the scope of c, and ρ ⊆ Dχ is a set of functions from the scope to the domain, called the relation of c.

A solution to the CSP instance P = 〈V,D,C〉 is a function from V to D whose restriction 1 to the scope of any constraint c ∈ C is one of the functions in the relation of c.

Example 2.2 Consider the CSP instance PAG = 〈V,D,C〉 where V = {1, 2, . . . , 10}, D = {0, 1}, and C = {c1, c2, . . . , c8}.

This instance has ten variables which must each be assigned the value 0 or 1, subject to 8 constraints. The constraints in C are defined as follows:

Note that each constraint except c8 allows every assignment to the variables of its scope. The constraint c8 does not allow the three variables of its scope all to take the value 0 simultaneously, but does allow all other assignments.

A straightforward calculation shows that this instance has exactly 7 ∗ 25 = 224 solutions.

In order to study the structural properties of CSP instances, that is, the way in which the constraint scopes overlap each other, we need the standard notion of a hypergraph.

Definition 2.3 A hypergraph is a pair H = 〈V, E〉, where V is an arbitrary set, called the vertices of H, and E is a set of subsets of V , called the hyperedges of H.

Definition 2.4 For any CSP instance P = 〈V,D,C〉, the structure of P, denoted σ(P), is the hypergraph 〈V, {χ | 〈χ, ρ〉 ∈ C}〉.

For any hypergraph H, the class of all CSP instances with structure H is denoted Ψ(H).

Example 2.5 Recall the CSP instance PAG defined in Example 2.2. The structure of PAG is the hypergraph HAG illustrated in Figure 1.

The set of vertices of HAG is the set {1, 2, . . . , 10}, and the eight hyperedges of HAG are the following subsets of these vertices: e1 = {1, 2}, e2 = {2, 3, 9}, e3 = {3, 4, 10}, e4 = {4, 5}, e5 = {5, 6, 9}, e6 = {6, 7, 10}, e7 = {7, 8, 9}, e8 = {1, 8, 10}.

As indicated in the Introduction, the decision problem for the general constraint satisfaction problem is NP-hard [Mackworth, 1977], so there has been considerable interest in finding more restricted problem classes whose instances can be recognized and solved in polynomial time.

Definition 2.6 A class I of CSP instances is called tractable if there is a polynomial time algorithm to decide membership of I, and a polynomial time algorithm which solves all instances in I.

A class I of CSP instances is called structural if I = ⋃H∈H Ψ(H) for some class of hypergraphs H.

1 To simplify the presentation we assume, throughout this paper, that every variable of a CSP instance is constrained; that is, every variable occurs in the scope of some constraint.

3 Guarded Decompositions

Two CSP instances with the same set of variables are called solution equivalent if they have the same set of solutions. All known tractable structural classes of CSP instances are characterized by showing that the instances they contain can be transformed into solution equivalent instances with simpler structure. The constraints of these transformed instances are obtained by calculating the relational joins of certain constraint relations in the original instances, and then projecting these onto new scopes. To describe this general transformation scheme we introduce the following terminology.

Definition 3.1 A guarded block of a hypergraph H is a pair 〈λ, χ〉 where the guard, λ, is a set of hyperedges of H, and the block, χ, is a subset of the vertices of the guard.

Definition 3.2 For any CSP instance P, and any guarded block 〈λ, χ〉 of σ(P ), the constraint generated by P on 〈λ, χ〉 is the constraint 〈χ, ρ〉, where ρ is the projection onto χ of the relational join of all the constraints of P whose scopes are elements of λ.

Given a CSP instance P, with structure H, and a collection of guarded blocks of H, we can generate constraints on each of these guarded blocks to obtain a new collection of constraints, and hence a newCSP instance. In some cases, if the guarded blocks are carefully chosen, this new instance will be solution equivalent to P, and so can be used to solve P. If this property holds for any CSP instance with structure H, then the collection of guarded blocks will be called a guarded decomposition of H, which is formally defined as follows:

Definition 3.3 A set of guarded blocks Ξ of a hypergraph H is called a guarded decomposition of H if for every CSP instance P = 〈V,D,C〉 ∈ Ψ(H), the instance P ′ = 〈V,D, C ′ 〉, where C ′ is the set of constraints generated by P on the members of Ξ, is solution equivalent to P .

How can we determine whether a given collection of guarded blocks is in fact a guarded decomposition? Theorem 3.5 below gives a simple and efficient way to answer this question, based on the following properties.

Definition 3.4 A guarded block 〈λ, χ〉 of a hypergraph H covers a hyperedge e of H if e is contained in χ.

A set of guarded blocks Ξ of a hypergraph H is called a guarded cover for H if each hyperedge of H is covered by some guarded block of Ξ.

A set of guarded blocks Ξ of a hypergraph H is called a complete guarded cover for H if each hyperedge e of H occurs in the guard of some guarded block of Ξ which covers e.

Theorem 3.5 A set of guarded blocks Ξ of a hypergraph H is a guarded decomposition of H if and only if it is a complete guarded cover for H.

Proof: Let Ξ be a set of guarded blocks of a hypergraph H = 〈V, E〉.

Suppose that Ξ is not a complete guarded cover for H. Choose e ∈ E such that there is no guarded block 〈λ, χ〉 ∈ Ξ for which e ∈ λ and e ⊆ χ. We will construct an instance Pe with structure H which will witness the fact that Ξ is not a guarded decomposition of H.

Let the domain of Pe be D = {0, 1}. For each edge f ∈ E, f ̸= e, let the constraint of Pe with scope f allow all mappings from f to D. Finally let the constraint of Pe with scope e, ce, allow all mappings from e to D except for the mapping that assigns the value 0 to all the vertices of e simultaneously.

Now let 〈λ, χ〉 be any guarded block in the set Ξ. If e ̸∈ λ then the constraint generated by Pe on 〈λ, χ〉 allows every assignment. On the other hand, if e ∈ λ, then, by the choice of e, we know that e ̸⊆ χ. In this case we observe that any projection of ce onto any proper subset of e allows all assignments. So again the constraint generated by Pe on 〈λ, χ〉 allows every assignment.

Since all constraints generated by Pe on all elements of Ξ allow every assignment, the resulting CSP instance is not solution equivalent to Pe, and hence Ξ is not a guarded decomposition of H.

For the converse, suppose that Ξ is a complete guarded cover for H. Let P be an arbitrary CSP instance with structure H. We have to show that the CSP instance PΞ obtained by taking the constraints generated by P on each element of Ξ is solution equivalent to P .

Clearly, any solution to P is a solution to PΞ. On the other hand, by the completeness of Ξ, and the construction of PΞ, the projection of any solution to PΞ onto any edge e ∈ E must be allowed by the constraint of P with scope e. Hence any solution to PΞ is also a solution to P .

4 Tractability

We have shown that guarded decompositions can be used to transform a given CSP instance to a solution equivalent instance which may have a different structure.

In order to be able to use guarded decompositions to identify tractable structural classes we need to impose some additional conditions to ensure we have the following properties.

Tractable construction It must be possible to generate each of the new constraints in polynomial time.

Tractable solution It must be possible to solve the resulting instances in polynomial time.

Tractable discovery It must be possible to obtain a guarded decomposition of the type we are considering for a given hypergraph (or else discover that no such decomposition exists) in polynomial time.

We will now consider extra conditions that can be imposed on a guarded decomposition to ensure that it has each of these properties.

4.1 Tractable Construction

The time complexity of a relational join operation is O(r k ), where k is the number of relations being joined, and r is the maximum number of tuples in any of these relations. Hence to ensure that we have the tractable construction property, it is sufficient to bound the number of constraint relations that need to be combined using the relational join operation. This can be done by bounding the number of hyperedges in the guard of any guarded block used in the decomposition.

Definition 4.1 The width of a set of guarded blocks is the maximum number of hyperedges in any of its guards.

For any fixed value of k, the class of guarded decompositions of width at most k has the tractable construction property.

4.2 Tractable Solution

One way to ensure that the new instances obtained by using a guarded decomposition have the tractable solution property, is to ensure that the structure of these new instances is acyclic [Beeri et al., 1983]. The property of being acyclic can be defined as follows:

Definition 4.2 A join tree of a hypergraph H is a connected tree, T, whose nodes are the hyperedges of H, such that, whenever the vertex x of H occurs in two hyperedges e1 and e2 of H then x occurs in each node of the unique path connecting e1 and e2 in T . In other words, the set of nodes of T in which x occurs induces a (connected) subtree of T .

A hypergraph is called acyclic if it has a join tree.

Theorem 4.3 ([Gyssens et al., 1994]) Any CSP instance whose structure is acyclic can be solved in polynomial time.

Definition 4.4 A join tree of a set of guarded blocks Ξ of H is a connected tree, T, whose nodes are the elements of Ξ, such that, whenever the vertex x of H occurs in two blocks of Ξ then x occurs in each block of the unique path connecting them in T. In other words, the set of nodes of T for which x occurs in the block induces a (connected) subtree of T .

A set of guarded blocks is acyclic if it has a join tree.

By Theorem 4.3, any class of acyclic guarded decompositions has the tractable solution property. Using Theorem 3.5 and Definition 4.4 we now show that an acyclic guarded decomposition can be obtained from an arbitrary acyclic guarded cover without increasing the width, or significantly increasing the number of guarded blocks, by adding appropriate additional guarded blocks to make a complete guarded cover.

Theorem 4.5 If the set of guarded blocks Ξ is an acyclic guarded cover for H then the set Ξ ∪ {〈{e}, e〉 | e ∈ E} is an acyclic guarded decomposition of H.

In view of this result, we shall focus on acyclic guarded covers and use them to define classes of decompositions.

4.3 Tractable Discovery

The class of hypergraphs having a guarded cover in some fixed class ∆, with width at most k, will be denoted C(∆, k).

Definition 4.6 A class of guarded covers ∆ will be called parameterized tractable 2 if for each value of k there exists a polynomial-time algorithm which, given any hypergraph H ∈ C(∆, k), returns a guarded cover of H with width at most k, and given any hypergraph H ̸∈ C(∆, k), reports failure.

It follows from the results above that if ∆ is a class of acyclic guarded covers, which is parameterized tractable, then C(∆, k) will be a tractable structural class of CSP instances, for each value of k.

5 Known Tractable Structural Classes

We will now show that many existing decomposition methods for the CSP can be defined in terms of finding acyclic guarded covers with particular special properties.

We first note that for historical reasons some existing decomposition methods for the CSP make use of extended guards that contain both vertices and hyperedges. To be able to present all of these methods in a uniform way we introduce the idea of transforming a CSP instance by adding a unary constraint cv, for each variable v, where cv = 〈{v}, {v}D〉. This corresponds to extending the structure of the instance to ensure that it includes a hyperedge for each variable.

Definition 5.1 Let H = 〈V,E〉 be any hypergraph. A guarded cover for the hypergraph 〈V, E ∪ {{v} | v ∈ V }〉 is called an extended cover for H.

The following result shows that the existence of an extended cover of width k is equivalent to the existence of a standard guarded cover of width k. This means that extended covers are simply a notational convenience and do not allow better decompositions.

Theorem 5.2 If a hypergraph H has an acyclic extended cover of width k, then H also has an acyclic guarded cover of width at most k with at most the same number of guarded blocks.

We also note that many existing decomposition methods are based on guarded covers in which every block is exactly the union of the edges of its guard.

Definition 5.3 A guarded cover Ξ is edge-defined if the block of each guarded block in Ξ is exactly the set of vertices contained in the hyperedges of its guard.

We can now characterize many known structural decomposition methods (see [Gottlob et al., 2000] for traditional definitions) in terms of a corresponding class of acyclic guarded covers with certain additional conditions.

2 The notion of being parameterized tractable that we have defined here is strictly weaker than the well-known notion of being fixed parameter tractable.

In each of the cases listed below (except for query decompositions), it has been shown that the additional conditions are sufficient to ensure that the corresponding class of acyclic guarded covers, ∆, is parameterized tractable. Hence, in all cases (except query decompositions), the class of CSP instances in C(∆, k) is a tractable structural class.

• A biconnected-component decomposition of a hypergraph is an edge-defined acyclic complete guarded cover, Ξ, satisfying an articulation condition:

• A cycle-hypercutset decomposition of a hypergraph H = 〈V,E〉 is an edge-defined acyclic complete guarded cover, Ξ, satisfying a simplicity condition:

• A hinge-tree decomposition of a hypergraph H is an edge-defined acyclic complete guarded cover, Ξ, satisfying a separation condition:

• A cycle-cutset decomposition of a hypergraph H is an edge-defined acyclic extended cover, Ξ, such that every hyperedge of every guarded block of Ξ consists of a single vertex, and Ξ satisfies a simplicity condition:

• A query decomposition of a hypergraphH = 〈V, E〉 is a pair 〈Ξ, T 〉 where Ξ is a complete edge-defined acyclic extended cover of H and T is a join tree of Ξ that satisfies a connectedness condition:

• A hypertree decomposition of a hypergraphH is a pair 〈Ξ, T〉, where Ξ is an acyclic guarded cover and T is a rooted join tree of Ξ, which satisfies the following descendant condition:

where D〈λ,χ〉 is the set of all descendants of 〈λ, χ〉 in T . The minimum width of any hypertree decomposition of a hypergraph H is called the hypertree width of H.

6 Comparing Decompositions

The relative strengths of different decomposition techniques derived from acyclic guarded covers can be compared using the measures developed by Gottlob et al [2000].

Definition 6.1 Let ∆1 and ∆2 be any two classes of guarded covers. We say that ∆1 generalizes ∆2 if there exists a value ε > 0 such that, for every k, C(∆2, k) ⊆ C(∆1, k + ε).

We say that ∆1 strongly generalizes ∆2 if ∆1 generalizes ∆2, and there exists k for which there does not exist ε > 0 with C(∆1, k) ⊆ C(∆2, k + ε).

Hypertrees have been shown to strongly generalize all the other parameterized tractable classes of decompositions defined in the previous section [Gottlob et al., 2000]. Furthermore it has recently been shown that the hypertree width of any hypergraph is at most three times the minimal possible width of any acyclic guarded cover [Adler, 2004]. It follows that hypertrees cannot themselves be strongly generalized by any other class of acyclic guarded covers.

However, we will show in the next section that it is possible to define a parameterized tractable class ∆ of acyclic guarded covers, such that for some families of hypergraphs, the minimal width of a guarded cover in ∆ is smaller than the hypertree width by some constant factor. Such an improvement allows the corresponding instances to be solved exponentially faster than by using hypertree decompositions.

Definition 6.2 Let ∆1 and ∆2 be any two classes of guarded covers. We say that ∆1 can be superior to ∆2 if there is some r > 1, such that for every k, C(∆2, rk) ̸⊆ C(∆1, k).

7 Spread Cuts

In this section we will define a new class of acyclic guarded covers, called spread cuts. We show that classes of instances with bounded spread cut width are tractable and that spread cuts can be superior to hypertrees. 3

Throughout this section, we will write ⋃ λ to refer to the vertices of a set of hyperedges λ; that is, ⋃ λ = ⋃e∈λ e.

Definition 7.1 Let H = 〈V, E〉 be a hypergraph and χ ⊆ V be a set of vertices. We say that two hyperedges e, f ∈ E are χ-adjacent if e ∩ f ̸⊆ χ.

A χ-path connecting e to f is a sequence e = e0, e1, . . . , er-1, er = f such that ei is χ-adjacent to ei+1, for i = 0, . . . , r - 1.

A set of hyperedges C ⊆ E is χ-connected if, for every pair of hyperedges in C, there is a χ-path connecting them.

A set of hyperedges is a hyperedge χ-component of H if it is a maximal non-empty χ-connected subset of E.

A non-empty set of vertices C is a vertex χ-component of H if there is some hyperedge χ-component Cχ for which C =

⋃ Cχ - χ. In this paper, unless otherwise stated, a component will mean a vertex component.

Example 7.2 Consider again the hypergraphHAG defined in Example 2.5 and illustrated in Figure 1.

Now consider the guarded block 〈λ, χ〉 with λ = {e2, e6} and χ = {3, 6, 7, 9, 10}.

There are three hyperedge χ-components: {e6}, {e1, e2, e7, e8} and {e3, e4, e5}. Hence, there are two vertex χ-components: {4, 5} and {1, 2, 8}.

There are four hyperedge ⋃ λ-components: {e2}, {e6}, {e1, e7, e8} and {e3, e4, e5}. Hence, there are two vertex

3 It is still an open research question whether hypertrees can be superior to spread-cuts.

⋃ λ-components: {4, 5} and {1, 8}. Notice that each vertex χ-component meets (has nonempty intersection with) exactly one vertex ⋃ λ-component.

This special property of this guarded block relies on χ being "large enough". If χ were empty, then there would be just one vertex χ-component and this component would meet

both vertex ⋃ λ-components. If we restrict the possible blocks for a given guard appropriately then we can polynomially bound the number of guarded blocks, whilst still getting effective decompositions. This motivates the following definition.

Definition 7.3 A guarded block 〈λ, χ〉 of a hypergraph H has unbroken components if each χ-component of H meets at most one ⋃ λ-component of H and {e1 ∩ e2 | e1, e2 ∈ λ} ⊆ χ.

A spread cut of H is an acyclic guarded cover for H in which all of the guarded blocks have unbroken components.

Example 7.4 Consider again the hypergraphHAG defined in Example 2.5 and illustrated in Figure 1.

The minimal width of any hypertree decomposition of HAG is three 4 .

The following set of guarded blocks is a spread cut of HAG of width two: 〈{e2, e6}, {3, 6, 7, 9, 10}〉, 〈{e3, e5}, {3, 4, 5, 6, 9, 10}〉, 〈{e2, e8}, {1, 2, 3, 8, 9, 10}〉, 〈{e3, e7}, {3, 7, 8, 9, 10}〉.

7.1 Spread Cuts are Parameterized Tractable

We will now define a canonical form for guarded blocks with unbroken components, and show that if a hypergraph H has a spread cut of width k, then it also has a spread cut of width at most k, in which each guarded block is canonical.

Definition 7.5 Let λ be any set of hyperedges of H. We define the label, Lλ(v), of any vertex of H to be the set of hyperedge

⋃ λ-components which include a hyperedge containing v. We say that a guarded block 〈λ, χ〉 is canonical if for each hyperedge e ∈ λ the vertices of e outside of χ are exactly those with a particular label. That is,

Theorem 7.6 If H has a spread cut of width k then H has a spread cut of width at most k, in which each guarded block is canonical.

Proof: Due to space limitations, we can only give an outline of the proof.

The idea is to show that, for any guarded block 〈λ, χ〉 with unbroken components, and for any hyperedge e ∈ λ, | ⋃v∈e-χ Lλ(v)| ≤ 2. Given this fact, we can start with any spread cut and, for each hyperedge of each guard, remove from the block any vertex with the same label as any vertices already outside of the block. It is straightforward to show that the result is still an acyclic guarded cover, and hence still a spread cut with the same width, where each guarded block is now canonical.

Using this canonical form, we can establish the following result.

Theorem 7.7 Spread cuts are parameterized tractable.

4 This is most easily shown by using the "Robbers and Marshals" characterization of hypertree width [Gottlob et al., 2003]. However, due to space restriction we omit this proof.

Proof: Due to space limitations, we can only give an outline of the proof.

The proof idea is that we only have to establish in polynomial time whether there exists a spread cut of width at most k in which each guarded block is canonical. We do this by first defining an object called a k-spread, which is a triple, 〈λ, χ, C〉, where 〈λ, χ〉 is any canonical guarded block with unbroken components, |λ| ≤ k, and C is a χ-component.

We then define the predicate k-split() (recursively) on kspreads. We say that k-split(〈λ, χ, C〉) holds if C is empty, or if there exists some canonical guarded block, 〈λs, χs〉, where χs ⊆ C ∪ χ and, for every k-spread 〈λs, χs, Cs〉:

It is easy to show that the number of k-spreads of a hypergraph H = 〈V,E〉 is at most (|E| + 1)k+2 . It follows (as in the corresponding proof for hypertrees, Lemma 14, Page 30, of Gottlob et al [2002]) that k-split(〈∅, ∅, V 〉) can be evaluated in at most |E|4k+5 steps.

Finally, we show that H has a spread cut with canonical guarded blocks of width at most k if and only if k-split(〈∅, ∅, V 〉). The only hard part of this proof is to show that the set of guarded blocks used in the proof of k-split(〈∅, ∅, V 〉) is a guarded cover. This proof is exactly analogous to the corresponding proof for the algorithm that finds normal form hypertree decompositions (See the proof of Property 1 in Lemma 13, Page 28, of Gottlob et al [2002]).

The proof of Theorem 7.7 also shows that classes of instances with bounded spread cut width are tractable.

7.2 Spread Cuts and Hypertrees

To establish that spread cuts strongly generalize all of the parameterized tractable decomposition methods listed in Section 5 excluding hypertrees we simply refer to the proofs of strong generalization given by Gottlob et al [2000] and observe that every hypertree (of small width) used to establish strong generalization in that paper is also a spread cut.

To show that spread cuts can be superior to hypertrees we establish the following result.

Proposition 7.8 There exists a family of hypergraphs Hn, n = 1, 2, 3, . . ., such that Hn has a spread cut with width 2n, but the hypertree width of Hn is at least 3n.

Proof: Due to space restrictions we can only give an outline of the proof.

The idea is to use n copies of the hypergraph HAG defined in Example 2.5 to construct Hn. We add edges linking vertices in different copies if they correspond to vertices of hyperedges that meet in HAG. Using the "Robbers and Marshals" characterization of hypertree width [Gottlob et al., 2003], we then show that the hypertree width of Hn is at least 3n. (If there are fewer than 3n marshals, the robber can always choose to play in the copy of HAG with at most two marshals on its hyperedges.)

Finally, the width 2n spread cut is just the spread cut of HAG with width 2 described in Example 7.4 "multiplied" over the n copies of HAG.

8 Conclusion

We have introduced the general notion of a guarded decomposition and shown how it can be used to describe many known tractable structural subproblems of the CSP. We have then defined a new form of decomposition, the spread cut, which sits in the same place in the generalization hierarchy as hypertrees. We have shown that spread cuts are parameterized tractable and that they allow us to obtain decompositions with a smaller width than any hypertree decomposition for some classes of hypergraphs.

It is an open question whether the general class of all acyclic guarded covers is itself parameterized tractable.