一句话：建立了以顶点完整性为参数的 FO/MSO 逻辑细粒度元定理及其 ETH 下界。
顶点完整性是介于顶点覆盖与树深之间的结构图参数。本文研究以该参数 k 为度量时，一阶逻辑（FO）与单子二阶逻辑（MSO）的算法元定理及细粒度复杂度取舍。作者通过核化预处理，将输入分别压缩到 $2^{O(k^2)}q$ 和 $2^{O(k^2+kq)}$ 规模，从而在 $2^{O(k^2q+q\log q)}+n^{O(1)}$ 时间内判定 FO，在 $2^{2^{O(k^2+kq)}}+n^{O(1)}$ 时间内判定 MSO。这些上界优于树深参数下的指数塔元定理，但差于顶点覆盖的对应界。最后，作者构造公式并在 ETH 下证明 FO 的 $2^{o(k^2q)}$ 与常数规模 MSO 的 $2^{2^{o(k^2)}}$ 下界，表明对 k 的二次依赖和中间复杂度不可避免。
Vertex Integrity is a graph measure which sits squarely between two more well-studied notions, namely vertex cover and tree-depth, and that has recently gained attention as a structural graph parameter. In this paper we investigate the algorithmic trade-offs involved with this parameter from the point of view of algorithmic meta-theorems for First-Order (FO) and Monadic Second Order (MSO) logic. Our positive results are the following: (i) given a graph $G$ of vertex integrity $k$ and an FO formula $\phi$ with $q$ quantifiers, deciding if $G$ satisfies $\phi$ can be done in time $2^{O(k^2q+q\log q)}+n^{O(1)}$; (ii) for MSO formulas with $q$ quantifiers, the same can be done in time $2^{2^{O(k^2+kq)}}+n^{O(1)}$. Both results are obtained using kernelization arguments, which pre-process the input to sizes $2^{O(k^2)}q$ and $2^{O(k^2+kq)}$ respectively. The complexities of our meta-theorems are significantly better than the corresponding meta-theorems for tree-depth, which involve towers of exponentials. However, they are worse than the roughly $2^{O(kq)}$ and $2^{2^{O(k+q)}}$ complexities known for corresponding meta-theorems for vertex cover. To explain this deterioration we present two formula constructions which lead to fine-grained complexity lower bounds and establish that the dependence of our meta-theorems on $k$ is the best possible. More precisely, we show that it is not possible to decide FO formulas with $q$ quantifiers in time $2^{o(k^2q)}$, and that there exists a constant-size MSO formula which cannot be decided in time $2^{2^{o(k^2)}}$, both under the ETH. Hence, the quadratic blow-up in the dependence on $k$ is unavoidable and vertex integrity has a complexity for FO and MSO logic which is truly intermediate between vertex cover and tree-depth.