# 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.1 The Scotland Yard Game  
The game is reminiscent of the board game _Scotland Yard_ where \(k\) detectives try to catch a thief on a map of London, but we of course play it on our input graph rather than in London (as in the board game, we forget about the direction of edges). At the beginning of the game, the detectives are all at a single vertex (at Scotland Yard) while the thief can choose any vertex of the graph as starting point. Now, both the thief and the detectives can move along edges of the graph and, as in the board game, whenever a detective and the thief are on the same vertex at any given moment, the thief immediately loses. On the other hand, while a detective is traveling from one vertex to another along an edge, she cannot catch the thief. Additionally, the thief can travel very quickly and he can make an arbitrary number of moves while a detective travels.  
The thief of course corresponds to the information that we trying to keep boxed in, the detectives correspond to the vertices that \"block\" the information and that must be taken into account during a recursion.  
Let us have a look at how two detectives, [PERSON] and [PERSON], can catch a thief, [PERSON], on a tree such as the one shown left in Figure 1. Suppose Scotland Yard is at the node \(a\) with [PERSON] and [PERSON] starting there and suppose [PERSON] starts at node \(h\). Now, [PERSON] moves from \(a\) to \(g\), but [PERSON] stays at \(a\). [PERSON] need not move in this case, but he could move to any node in the subtree rooted at \(g\). Suppose he does not move. Next, [PERSON] stays at node \(g\) while [PERSON] moves from \(a\) past him to node \(h\), forcing [PERSON] to move away from there. Since he cannot move past [PERSON] on \(g\), he has to move somewhere downward, say to \(m\). Now it is [PERSON]'s turn once more, who moves past [PERSON] from \(g\) to \(i\). [PERSON] gets a bit panicky at this point and uses his last chance to quickly move from \(m\) to \(j\) before [PERSON] arrives at \(i\). Naturally, [PERSON] can now move to \(j\), forcing [PERSON] further downwards to either \(k\) or \(l\). Finally, [PERSON] catches [PERSON] by moving to his position.  
In a second example, consider a ring such as the one shown right in Figure 1. This time, [PERSON] and [PERSON] starting at \(a\) will have a much harder time catching [PERSON]--more precisely, they cannot: they  
Figure 1: (**Left**) a tree on which, in the Scotland Yard game, two detectives, [PERSON] and [PERSON], suffice to catch a thief wherever he starts. The _tree width_ of the tree, which is defined as the necessary number of detectives minus 1, is hence 1; (**Right**) in contrast, on a cycle, [PERSON] and [PERSON] _must_ enlist the help of a third detective, [PERSON], to catch the thief. Hence, the tree width of a cycle is 2.  
can endlessly chase him around in circles, but will not catch him if he moves sensibly. Thus, suppose [PERSON] and [PERSON] enlist the help of [PERSON], a third detective who also starts at \(a\). The three detectives can catch [PERSON] in as little as three steps: first, [PERSON] moves to \(e\), forcing [PERSON] into either the left or the right half of the circle. Say, he moves to \(d\). Second, [PERSON] moves to the middle vertex of the half [PERSON] chose, that is, to \(c\), forcing him either to \(b\) or to \(d\). If he moves to \(b\), [PERSON] can catch him there, if he moves to \(d\), [PERSON] can.