Example 8. Figure 7 exhibits a graph (the extended graph structure of the value-based system of Example 2)
and a tree decomposition of it. The width of the tree decomposition is 2, and it is not difficult to see that this is optimal. Hence the treewidth of the graph in the figure is 2.

![0_image_0.png](0_image_0.png)

## 4.1 Linear-Time Tractability For Value-Based Systems With Extended Graph Structures Of Bounded Treewidth

We are going to establish the following result.

Theorem 3. *The problems* SUBJECTIVE and OBJECTIVE ACCEPTANCE *can be decided in linear time for valuebased systems whose extended graph structure has bounded treewidth.*
To achieve tractability we have to pay a price in generality: The mentioned hardness results of [14, 13]
imply that if SUBJECTIVE ACCEPTANCE is fixed-parameter tractable for any parameter p, then, unless P = NP,
parameter p cannot be bounded by a function of any of the following three parameters: the treewidth of the graph structure, the treewidth of the value graph, and the value-width. This even holds if the bounding function is exponential. Indeed, the treewidth of the extended graph structure can be arbitrarily large for value-based systems where one of these three parameters is bounded by a constant.

The reminder of this section is devoted to a proof of Theorem 3. We shall take a logic approach and use the celebrated result of Courcelle [9], which states that all properties that can be expressed in a certain formalism (Monadic Second-Order logic, MSO) can be checked in linear time for graphs (or more generally, for finite structures) of bounded treewidth. Courcelle's Theorem is constructive in the sense that it not only promises the existence of an algorithm for the particular problem under consideration, but it provides the means for actually producing such an algorithm. The algorithm produced in this general and generic way leaves much room for improvement and provides the basis for the development of problem-specific and more practical algorithms.

In the following we use Courcelle's result as laid out by Flume and Grohe [17]. Let S denote a finite relational structure and ϕ a sentence in monadic second-order logic (MSO logic) on S. That is, ϕ may contain quantification over atoms (elements of the universe) and over sets of atoms. Furthermore, we associate with the structure S its *Gaifman graph* G(S), whose vertices are the atoms of S, and where two distinct vertices are joined by an edge if and only if they occur together in some tuple of a relation of S. We define the *treewidth of structure* S
as the treewidth of its Gaifman graph G(S). Now Courcelle's theorem states that for a fixed MSO sentence ϕ and a fixed integer k, one can check in linear time whether ϕ holds for a given relational structure of treewidth at most k. The proof of Theorem 3 boils down to the following two tasks:
Task A. To represent a value-based system F and a query argument x1 by a relational structure S[**F, x**1] such that bounded treewidth of the extended graph structure of F implies bounded treewidth of S[**F, x**1].