Elementary first-order model checking for sparse graphs
CoRR(2024)
摘要
It is known that for subgraph-closed graph classes the first-order model
checking problem is fixed-parameter tractable if and only if the class is
nowhere dense [Grohe, Kreutzer, Siebertz, STOC 2014]. However, the dependency
on the formula size is non-elementary, and in fact, this is unavoidable even
for the class of all trees [Frick and Grohe, LICS 2002]. On the other hand, it
is known that the dependency is elementary for classes of bounded degree [Frick
and Grohe, LICS 2002] as well as for classes of bounded pathwidth [Lampis,
ICALP 2023]. In this paper we generalise these results and almost completely
characterise subgraph-closed graph classes for which the model checking problem
is fixed-parameter tractable with an elementary dependency on the formula size.
Those are the graph classes for which there exists a number d such that for
every r, some tree of depth d and size bounded by an elementary function of
r is avoided as an (≤ r)-subdivision in all graphs in the class. In
particular, this implies that if the class in question excludes a fixed tree as
a topological minor, then first-order model checking for graphs in the class is
fixed-parameter tractable with an elementary dependency on the formula size.
更多查看译文
AI 理解论文
溯源树
样例
生成溯源树,研究论文发展脉络
Chat Paper
正在生成论文摘要