# Vertex Cover Reconfiguration and Beyond +
## 6 FPT Algorithms
### FPT Algorithm for Nowhere Dense Graphs  
In this section, we present a more general result, showing that the reconfiguration variant of every first-order definable optimization problem parameterized by \(\ell\) is fixed-parameter tractable on every fixed nowhere dense class of graphs. Let us quickly recall the necessary definitions from logic. For our purpose, it suffices to consider first-order logic over the vocabulary of coloured graphs. We refer to the textbook [26] for extensive background on logic. Let \(A,B\) be two unary relation symbols and \(E\) a binary relation symbol. We call \(\{E,A,B\}\) the vocabulary of graphs with two colours \(A\) and \(B\). First-order formulas over the vocabulary of coloured graphs are formed from atomic formulas \(x=y\), \(E(x,y)\), \(A(x)\) and \(B(x)\), where \(x,y\) are variables (we assume that we have an infinite supply of variables), by the usual Boolean connectives \(\
eg\) (negation), \(\wedge\) (conjunction) and \(\vee\) (disjunction) and existential and universal quantification \(\exists x,\forall x\), respectively. The free variables of a formula are those not in the scope of a quantifier, and we write \(\varphi(x_{1},\ldots,x_{k})\) to indicate that the free variables of the formula \(\varphi\) are among \(x_{1},\ldots,x_{k}\). To define the semantics, we inductively define a satisfaction relation \(\models\). Let \(G\) be a graph and \(A,B\subseteq V(G)\). For simplicity, we do not distinguish between \(A\) as a symbol and \(A\) as a set. For a formula \(\varphi(x_{1},\ldots,x_{k})\), and \(v_{1},\ldots,v_{k}\in V(G)\), \(G\models\varphi(v_{1},\ldots,v_{k})\) means that \(G\) satisfies \(\varphi\) if the free variables \(x_{1},\ldots,x_{k}\) are interpreted by \(v_{1},\ldots,v_{k}\). If \(\varphi(x_{1},x_{2})=E(x_{1},x_{2})\) is atomic, then \(G\models\varphi(v_{1},v_{2})\) if \((v_{1},v_{2})\in E(G)\). Similarly, if \(\varphi(x)=A(x)\), then \(G\models\varphi(v)\) if \(v\in A\). The meanings of the equality symbol, the Boolean connectives and the quantifiers are the usual ones. Let \(\varphi(X)\) be a first-order formula that has a free set variable \(X\). For example, the vertex cover problem is defined by the formula:  
\[\varphi(X)=\forall x\forall y(\
eg E(x,y)\lor X(x)\lor X(y)).\]  
As another example, we can define dominating sets by the formula:  
\[\varphi(X)=\forall x(X(x)\lor\exists y(X(y)\wedge E(x,y))\]  
and independent sets by the formula:  
\[\varphi(X)=\forall x\forall y((X(x)\wedge X(y)\wedge x\
eq y)\to\
eg E(x,y)).\]  
Naturally, we can define a reconfiguration variant for each such formula \(\varphi\). Given two sets \(S,T\subseteq V(G)\), we ask for a sequence \(S_{1},\ldots,S_{t}\), \(S_{1}=S\) and \(S_{t}=T\) such that \(G\models\varphi(S_{i})\) for all intermediate configurations \(S_{i}\). We call the corresponding decision problem \(\varphi\)-reconfiguration, and we refer to a solution of a problem instance as a \(\varphi\)-reconfiguration sequence. Nowhere dense graph classes were introduced by [PERSON] and [PERSON] [27] as a very general model of uniform sparseness in graphs. We refer to the textbook [28] for the formal definition of the notion of nowhere denseness and for more background on its theory. For our purpose, it is sufficient to note that most familiar classes of sparse graphs are nowhere dense, e.g., every proper minor closed class and every class of bounded degree is nowhere dense. We will prove the following theorem. Theorem 4.1: _Let \(\varphi(X)\) be a first-order formula over the vocabulary of graphs with a free set variable; let \(\mathcal{C}\) be a nowhere dense class of graphs; let \(\epsilon>0\) be a real; and let \(\ell\geq 1\) be an integer.