The NIP characterization of tractable model-checking on hereditary classes

Let $\mathcal{C}$ be a hereditary class of relational structures. Here, model-checking on $\mathcal{C}$ is tractable if there is an algorithm that, on input a structure $M\in\mathcal{C}$ and an $\mathsf{FO}$-sentence $\phi$, decides whether $M\models\phi$ in time $f(|\phi|)\cdot |M|^{\mathcal{O}(1)}$ for some computable function $f$. The class $\mathcal{C}$ is NIP if its theory does not have the independence property. NIP characterization of tractability. The model-checking problem on $\mathcal{C}$ is fixed-parameter tractable if, and only if, $\mathcal{C}$ is NIP. All known hereditary classes of graphs and relational structures with tractable model-checking are NIP, and the conjecture proposes that NIP is also necessary for tractability in every hereditary class.