# A Gentle Introduction to Applications of Algorithmic Metatheorems for Space and Circuit Classes
## 3 An Algorithmic Metatheorem for Logspace and Its Applications
### Applications: High-Hanging Fruits I--Cycle Modularity Problems  
The introduction hinted already at applications of algorithmic metatheorems to graphs that do _not_ have bounded tree width. The idea was to develop algorithms that work in two phases: first, we test whether the input graph happens to have tree width at most \(k\) for some appropriately chosen constant \(k\) and, if so, we use the algorithmic metatheorem to solve the problem. Second, if the graph has tree width larger than \(k\), we use _another_ algorithm that makes good use of this knowledge. This approach is well established in the context of Courcelle's Theorem and, in some cases, also works for its logspace version:  
**Theorem 7**.: _The problem even-cycle = { \(G\mid G\) is an undirected graph containing a cycle of even length\(\}\) can be decided in logarithmic space._  
Proof Ideas.: There are two core observations needed to prove the theorem: first, we can describe the property \"the graph has an even cycle\" using monadic second-order logic. We ask whether there exist two (nonempty, disjoint) subsets of the _edges_, which we call the red and the green edges, such that each vertex is either incident to none of these edges or to exactly one red and one green edge. (Again, we use the trick of subdividing edges so that we can formally quantify over subsets of the vertices even though we wish to quantify over subsets of the edges.) Second, [PERSON] [6] has proved the following: _There is a number \(k\) such that every undirected graph \(G\) of tree width more than \(k\) has an even cycle._  
Together, these observations yield the following logspace algorithm for the language even-cycle: Upon input of a graph \(G\), first test whether its tree width is more than \(k\) and, if so, accept the input. Otherwise, compute a tree decomposition and run an appropriate tree automaton to decide the problem.  
It is worthwhile observing that even-cycle does not only lie in logarithmic space, but is actually complete for it (as can be seen by a simple reduction from the L-complete undirected acyclicity problem: just subdivide each edge). In contrast, the linear time bound on even-cycle resulting from [PERSON]'s classical theorem is _tight_, but even-cycle is _not_ complete for linear time (unless \(\mathrm{L}=\mathrm{P}\)).  
The results on the even cycle problem may have made you curious about other problems where the objective is to find a cycle whose length has a certain property (at least, they made me curious). First, the _odd_ cycle problem turns out to be algorithmically easier for the simple reason that if there is a \"walk\" (unlike a path or a cycle, a walk may contain the same vertex several times) of odd lengths returning to the start vertex, there must be a cycle of odd lengths in the graph. This makes it relatively easy to reduce the odd cycle problem to the undirected reachability problem, which shows that odd-cycle is also complete for logarithmic space.  
Second, what about the more general question of whether there exists a cycle in an undirected graph whose length modulo is some number \(m\) is some number \(x\)? The even cycle problem is this problem for \(m=2\) and \(x=0\), for the odd cycle problem \(m=2\) and \(x=1\). It turns out that [PERSON]'s result holds for _all_\(m\geq 2\) for \(x=0\), that is, [PERSON] has shown [6] that _for all_\(m\geq 2\)_there exists a number \(k\) such that all graphs of tree width at least \(k\) have a cycle whose length modulo \(m\) is \(0\). This means that all \"cycle modularity problems\" for \(x=0\) are complete for logarithmic space. In sharp contrast, the complexity of this problem for \(m=3\) and \(x=1\) is completely open; the best upper bound is NP!