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

Jan Jedelský · 2026

Read On first-order model checking parameterized by the number of variables by Jan Jedelský (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2604-22493.txt.

Introduction

Jedelský studies first-order model checking, whether a graph satisfies a logical sentence, parameterized by variable-name count. That parameter is far stricter than quantifier rank, since a sentence can reuse few names across many quantifiers. Earlier work showed hardness by quantifier rank and a slower algorithm by variable count. Fast algorithms were known only for special graph families under the rank parameter. Jedelský asks which families admit such an algorithm, characterizing them in the monotone setting and proving a weaker result for hereditary families.

Catalog record

CREATORJan Jedelský
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE48915
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2604.22493

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

On first-order model checking parameterized by the number of variables Jan Jedelský Abstract The first-order (FO) model checking problem asks, given an FO sentence ϕ \phi and a graph G G , whether G G is a model of ϕ \phi . 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. Faculty of Informatics, Masaryk University, Brno, Czech [email protected]://orcid.org/0000-0001-9585-2553 \crefname theoremtheoremtheorems \Crefname theoremTheoremTheorems \crefformat theorem#2theorem #1#3 \Crefformat theorem#2Theorem #1#3 \crefname corollarycorollarycorollaries \Crefname corollaryCorollarycorollaries \crefformat corollary#2corollary #1#3 \Crefformat corollary#2Corollary #1#3 \crefname lemmalemmalemmas \Crefname lemmaLemmaLemmas \crefformat lemma#2lemma #1#3 \Crefformat lemma#2Lemma #1#3 \crefname questionquestionquestions \Crefname questionQuestionQuestions \crefformat question#2question #1#3 \Crefformat question#2Question #1#3 \crefname conjectureconjectureconjectures \Crefname conjectureConjectureConjectures \crefformat conjecture#2conjecture #1#3 \Crefformat conjecture#2Conjecture #1#3 \crefname claimclaimclaims \Crefname claimClaimClaims \crefformat claim#2claim #1#3 \Crefformat claim#2Claim #1#3 ccs Theory of computation Logic ccs Theory of computation Fixed parameter tractability ccs Mathematics of computing Graph theory keywords Model checking, first-order logic, tree-depth, shrub-depth † † runningauthor: J. Jedelský † † copyright: Jan Jedelský † † funding: The author has been supported by the project 26-21334S of the Czech Science Foundation. † † editors: John Q. Open and Joan R. Access † † event-title: 42nd Conference on Very Important Topics (CVIT 2016) † † event-shorttitle: CVIT 2016 † † event-acronym: CVIT † † year: 2016 † † event-date: December 24–27, 2016 † † event-location: Little Whinging, United Kingdom † † series-volume: 42 † † articleno: 23 1 Introduction The first-order (FO) model checking problem asks, given a graph G and an FO formula \phi , whether G\models\phi . The FO model checking problem thus generalizes all problems expressible in first-order logic. Given an n -vertex graph G and FO formula \phi using k distinct variables, the well-known naive evaluation algorithm decides G\models\phi in time \mathcal{O}(|\phi|\cdot n^{k}) . That is, the FO model checking problem parameterized by the number of variables can be solved in \mathsf{XP} -time. Downey, Fellows, and Taylor [ 2 ] proved that the FO model checking parameterized by the quantifier rank of the formula is \mathsf{AW[*]} -hard, thus giving rise to the following natural question: Question 1 . For which graph classes \mathcal{C} does it hold that FO model checking admits an \mathsf{FPT} -time algorithm when restricted to inputs from \mathcal{C} and parameterized by the quantifier rank of the formula? Over the last few decades, there has been significant progress towards \Cref q:fo-mc-param-by-qr. However, the naive evaluation algorithm runs in \mathsf{XP} -time even when parameterized by the number of variables rather than the quantifier rank of the formula. Hence, it seems natural to also ask the following question: Question 2 . For which graph classes \mathcal{C} does it hold that FO model checking admits an \mathsf{FPT} -time algorithm when restricted to inputs from \mathcal{C} and parameterized by the number of variables of the formula? We investigate \Cref q:fo-mc-param-by-num-var in the settings where the class \mathcal{C} is monotone or hereditary. We fully answer the question for monotone graph classes: ?? ?? \Cref thm:unbounded-tree-depth-hardness together with \Cref col:algo-tree-depth immediately gives the following solution to \Cref q:fo-mc-param-by-num-var in the monotone setting: Theorem 3 (store=thm:tree-depth-is-the-limit,label=thm:tree-depth-is-the-limit) . Assume that \mathsf{FPT} \neq \mathsf{AW[*]} . Let \mathcal{C} be a monotone class of graphs. Then, FO model checking is \mathsf{FPT} when restricted to inputs from \mathcal{C} and parameterized by the number of variables if and only if \mathcal{C} has bounded tree-depth. We conjecture that a statement similar to \Cref thm:tree-depth-is-the-limit holds also for hereditary classes with tree-depth replaced by shrub-depth. We prove the existence of an algorithm and a conditional lower bound supporting our conjecture: ?? ?? We defer the definition of a flipped half-graph and a layerwise flipped tP_{t} to \Cref def:half-graph-paths-flips. Note that, while we do not know how to compute the flip from Item ( 2 ), it is known to exist (when Item ( 1 ) does not hold): Mählmann [ 6 ] proved that every hereditary class \mathcal{C} of unbounded shrub-depth contains a flipped half-graph of order t for all t\in\mathbb{N} or \mathcal{C} contains a layerwise flipped tP_{t} for all t\in\mathbb{N} . Outline of the paper In \Cref sec:prelim, we overview the notation and the relevant concepts from graph theory and finite model theory. The main result of the article is proven in two sections – the algorithms are described in \Cref sec:algo, and the hardness is proven in \Cref sec:hardness. Finally, we discuss conclusions and open questions in \Cref sec:concl. 2 Preliminaries We briefly recall basic notation. Given a graph G , we denote by V(G) its vertex set and by E(G) its edge set. We also denote by N_{G}(u) the open neighborhood of a vertex u\in V(G) , and by N_{G}[u] the closed neighborhood. Finally, we denote by G[X] the subgraph of G induced by a set X\subseteq V(G) . Let c\in\mathbb{N} be a natural number. A c -colored graph has each vertex colored by exactly one of c colors; usually, we assume the set of colors is [c]:=\{1,2,\ldots,c\} . An isomorphism of colored graphs has to respect the colors. We only consider simple graphs, but most of our results could be extended to other relational structures. We say that a function f(\bar{a},\bar{b},\bar{c}) is elementary for any fixed \bar{b} if, for every \bar{b} , the function g_{\bar{b}}(\bar{a},\bar{c}):=f(\bar{a},\bar{b},\bar{c}) is elementary. 2.1 Half-graphs, paths, and flips Let G be a graph and let \mathcal{P} be a partition of a subset \bigcup\mathcal{P} of the vertex set of G . A \mathcal{P} -flip is a symmetric relation F on \mathcal{P} . We denote by F\oplus G the following graph: V(F\oplus G)=V(G) , and uv\in E(F\oplus G) is decided as follows: • If \{u,v\}\not\subseteq\bigcup\mathcal{P} , then uv\in E(F\oplus G) if and only if uv\in E(G) . • Otherwise, there are U,V\in\mathcal{P} such that u\in U and v\in V . Then, uv\in E(F\oplus G) if and only if ( uv\in E(G) xor (U,V)\in F ). In a slight abuse of notation, we sometimes say that a graph H is a \mathcal{P} -flip of G if there is a \mathcal{P} -flip F such that H=F\oplus G . If \mathcal{P}=\{P\} has only one part, then we write P -flip instead of \{P\} -flip. A half-graph H_{t} of order t is a bipartite graph on 2t vertices a_{1},\ldots,a_{t} , and b_{1},\ldots,b_{t} such that a_{i}b_{j}\in E(H_{t}) if and only if i\leq j . We always assume that

Read the complete text