# A Gentle Introduction to Applications of Algorithmic Metatheorems for Space and Circuit Classes
## 1 Introduction
### The Range of Applications of Algorithmic Metatheorems  
The power of algorithmic metatheorems lies in their ease of application. If our student had known about [PERSON]'s Theorem, finding a linear-time algorithm for the vertex cover problem on trees would have been much easier for her: The problem can be described in monadic second-order logic (as we will see later) and trees are clearly \"tree-like\", so the theorem tells her (and us) that there is a linear-time algorithm for the problem. Admittedly, the vertex cover problem on trees is not the most difficult problem imaginable from an algorithmic point of view and using Courcelle's Theorem to solve it might seem like a bit of an overkill, but by the logspace version of Courcelle's Theorem, we also get a logspace algorithm for this problem for free and coming up with such an algorithm directly is quite difficult (readers are cordially invited to give it a try). Furthermore, we will see that there are many problems that can be formulated in monadic second-order logic, which immediately shows that all of these problems can be solved both in linear time and in logarithmic space on tree-like graphs.  
To make the vertex cover problem accessible to algorithmic metatheorems (and to allow our student to apply divide-and-conquer to it), we simplified the problem quite radically: we simply _required_ that the inputs must be trees rather than general graphs. Instead of only trees, algorithmic metatheorems typically allow us to consider input graphs that are only tree\"-like\", but this is still a strong restriction. It is thus somewhat surprising that algorithmic metatheorems can _also_ be used in contexts where the inputs are _not_ tree-like graphs. The underlying algorithmic approach is quite ingenious: Upon input of a graph, if the graph is tree-like, we apply an algorithmic metatheorem, and if the graph is not tree-like, it must be \"highly interconnected internally\", which we may be able to use to our advantage to solve the problem.  
One deceptively simple problem where the just-mentioned approach works particularly well is the _even cycle problem_, which just asks whether there is a cycle of even length in a graph (in the graph \(\cancel{\circ}\), the black vertices form the only even cycle). It is not difficult to show that, just like the vertex cover problem and just like about any other interesting problem, the even cycle problem can be described in monadic second-order logic, and thus be solved efficiently on tree-like graphs. Now, what about highly interconnected graphs that are _not_ tree-like? Do their many edges somehow help in deciding whether the graph has an even cycle? It turns out that the answer is a resounding \"yes\": such graphs _always_ have an even cycle [6]. In other words, we can solve the even cycle problem on _arbitrary_ graphs as follows: if the input graph is not tree-like, simply answer \"yes\", otherwise apply Courcelle's Theorem to it.  
Naturally, we will not always be so lucky that the to-be-solved problem more or less disappears for non-tree-like graphs, but we will see in the course of this paper that there is a surprisingly large range of problems where algorithmic metatheorems play a key role in the internals of larger algorithms for solving them.