On first-order model checking parameterized by the number of variables

Jan Jedelský

The first-order (FO) model checking problem asks, given an FO sentence $\varphi$ and a graph $G$, whether $G$ is a model of $\varphi$. This problem is $\mathsf{AW}[\ast ]$-hard when parameterized…