# A Gentle Introduction to Applications of Algorithmic Metatheorems for Space and Circuit Classes
## 2 The Concepts and Ideas Behind Courcelle's Theorem
### Decomposing the Problems: Tree Decompositions
#### 2.2.2 Decompositions Are Game Strategies  
For the first graph, the tree, _two_ detectives have a \"winning strategy\" for catching [PERSON], no matter where he starts. For the second graph, the cycle, _three_ detectives have such a strategy (but two do not). The strategies can be described as _trees_ whose nodes contain sets of positions of the detectives during their hunt for [PERSON]: at the root, all detectives are at Scotland Yard. For a positioning of the detectives, the children of this position in the tree are the next positions for the detectives, depending on where [PERSON] might be. Figure 2 shows the strategy of the three detectives for the cycle graph with black vertices denoting positions where the detectives are. The mathematical terminology for these strategies is, of course, different: The \"strategy trees\" are known as _tree decompositions_ of the graph. For each node of the tree, the set of positions where the detectives are is called the _bag_ of the node. These bags contain exactly the vertices along which information might \"flee\" from a smaller subgraph towards the root.  
During a divide-and-conquer algorithm, we (only) need to keep track of the vertices in bags and consider (only) all possible ways in which they can be part of an optimal solution. Indeed, the runtime of algorithms that \"walk up the tree decomposition\" is typically linear in the size of the tree, but exponential in the size of the bags, making the number of detectives needed a crucial parameter.  
It is no coincidence that two detectives are needed to corner [PERSON] on a tree while three are necessary on a cycle: a graph is a tree if, and only if, two detectives suffice. For this reason, the number of detectives minus one is called the _tree width_ of the graph. The tree width of a tree is then \(1\), the tree width of a cycle is \(2\), while the tree width of the \(n\)-vertex clique \(K_{n}\) is \(n-1\).  
Let me make two observations concerning possible strategies of the detectives: First, if necessary, the detectives can always adapt their strategy so they never need to \"return\" to a vertex that they have left earlier, since they only leave a vertex when [PERSON] is cornered into an area of the graph from which the left vertex is no longer accessible to [PERSON]. This means that when we have a look at all nodes of the tree decomposition tree whose bags contain a certain vertex (like the Scotland Yard vertex), these nodes will form a connected component of the tree. Second, for each edge of the graph there will be a bag containing the two endpoints of this edge since, otherwise, [PERSON] could always go back and forth along this edge without ever being caught.  
Figure 2: The “strategy tree” in the Scotland Yard game for catching a thief on a circle using three detectives. A tree decomposition of the circle is obtained from this strategy tree by replacing the small graphs shown in the nodes by so-called “bags” consisting of the black vertices in each of the small graphs.