9.4.1. Feedback Vertex Set for Cyclomatic Weight Functions

In this section, we prove that a \(2\)-approximation of an optimal undirected feedback vertex set can be obtained easily, provided the weight function is cyclomatic. To define what a cyclomatic weight function is, we need some terminology from linear algebra. Specifically, we need finite fields and finite vector spaces. We review these first. Then we introduce cyclomatic weight functions and prove that a \(2\)-approximation of an optimal undirected feedback vertex set is easy to obtain for such weight functions.