On first-order model checking parameterized by the number of variables
Publish this paper in The AIPR Journal
Are you an author? Turn this AI review into a permanent, citable journal entry with a cover, open comments, and Scholar metadata.
AIPR assessment
This is a hard, specialized theory problem in a well-developed area, not an uncrowded niche, so the bar is high even for clean structural results. The paper’s strengths reinforce each other: a sharp classification theorem, a complete proof of the tractable side, and a matching hardness story in the monotone case give the work real coherence. The main weaknesses also interact: the hereditary lower bound is conditional, and the practical applicability is limited by the purely structural nature of
Abstract
The first-order (FO) model checking problem asks, given an FO sentence $φ$ and a graph $G$, whether $G$ is a model of $φ$. This problem is known to be $\mathsf{AW[*]}$-hard when parameterized by the quantifier rank of the formula. A classical algorithm decides this problem in XP-time parameterized by the number of variables in the formula. Due to $\mathsf{AW[*]}$-hardness, it is natural to ask about the complexity of the problem when restricted to some well-behaved class of graphs. There are many results describing graph classes $\mathcal{C}$ such that the FO model checking problem restricted to $\mathcal{C}$ admits an $\mathsf{FPT}$-time algorithm when parameterized by the quantifier rank of the formula. Parameterization by the quantifier rank is significantly more restrictive than parameterization by the number of variables. We investigate the graph classes $\mathcal{C}$ for which the FO model checking problem restricted to $\mathcal{C}$ admits an $\mathsf{FPT}$-time algorithm when parameterized by the number of variables in the formula. We characterize these classes in the monotone setting, and prove a slightly weaker result in the hereditary setting.
Score Breakdown
More from this week
- Agentic World Modeling: Foundations, Capabilities, Laws, and Beyond
- How Hard is it to Decide if a Fact is Relevant to a Query?
- Railway Artificial Intelligence Learning Benchmark (RAIL-BENCH): A Benchmark Suite for Perception in the Railway Domain
- Entrywise Low-Rank Approximation and Matrix \(p \rightarrow q\) Norms via Global Correlation Rounding
- Cuts and Gauges for Submodular Width