CS Paper Radar

A Logic for Minor-Free Graph Classes: Model Checking, Dependence, and Combinatorial Reconfiguration

Nikolas Mählmann, Patrice {Ossona de Mendez}, Nicole Schirrmacher, Sebastian Siebertz, Giannos Stamoulis, {Dimitrios M. } Thilikos, Alexandre Vigny

cs.LO cs.DMmath.LO ·submitted 2026-10-04 14:34 UTC · v1

Abstract

We introduce \emph{sub-connectivity logic}, denoted by $\textsf{FOscon}$, an extension of first-order logic for graphs with a specified set $Z$ of admissible edges. Its additional atom $\textsf{scon}(x,y;\bar z)$ asserts that $x$ and $y$ are connected by a path using only edges of $Z$ and avoiding the vertices in $\bar z$. Our main structural result states that, for every weakly sparse graph class $\mathscr C$, the class of all expansions of graphs in $\mathscr C$ by rooted spanning forest orders has bounded twin-width if and only if $\mathscr C$ excludes a fixed minor. When $\mathscr C$ excludes a fixed minor, we can also compute an additional linear order that preserves bounded twin-width in polynomial time. We translate $\textsf{FOscon}$ into first-order logic over an expansion by a depth-first spanning forest order of the admissible-edge graph. Combining this translation with our structural result, we obtain a model checking algorithm for $\textsf{FOscon}$ with running time $f(|φ|,h(G))\cdot |G|^c$, where $f$ is computable, $c$ is an absolute constant, and $h(G)$ is the Hadwiger number of $G$. The translation and model-checking algorithm extend to binary relational structures, with the Hadwiger number measured on the Gaifman graph. For a graph class $\mathscr C$ let $\mathscr C_Z:=\{(G,Z):G\in\mathscr C,\ Z\subseteq E(G)\}$. We show that for every weakly sparse graph class $\mathscr C$, the class $\mathscr C_Z$ is monadically dependent for $\textsf{FOscon}$ if and only if $\mathscr C$ excludes a fixed minor. For monotone classes that admit efficient minor encodings, a corresponding hardness result makes this frontier computationally tight. We give applications to combinatorial reconfiguration and solution discovery problems, and study a guarded extension of $\textsf{FOscon}$ motivated by database queries.

Closest papers

Nearest neighbours by meaning across the whole index.

First-Order Model Checking on Monadically Dependent Graph Classes

cs.LO cs.DMcs.DSmath.CO+1 ·2026-11-05 ·Jan Dreier, Nikolas Mählmann, Szymon Toruńczyk
similarity 0.72
Abstract

Monadically dependent graph classes are those in which first-order logic cannot encode all graphs. They include all nowhere dense classes and all classes of bounded twin-width. We show that first-order model checking is fixed-parameter tractable on every monadically dependent graph class. Together with the known hardness result for hereditary classes that are not monadically dependent, this gives a complete characterization of the hereditary graph classes with fixed-parameter tractable first-order model checking. This resolves a central open problem in algorithmic model theory. Our proof combines ideas from structural graph theory (graph decompositions), finite model theory (locality of first-order logic), and model theory (counting types). In particular, we show that in monadically dependent classes, tuples of fixed length have only $|U|^{O(1)}$ types of fixed quantifier rank over any set of parameters $U$.

0.18

Monadically Dependent Graph Classes Have Almost Bounded Merge-Width

cs.DM cs.DScs.LOmath.CO+1 ·2026-11-04 ·Jan Dreier, Nikolas Mählmann, Michał Pilipczuk, Szymon Toruńczyk
theory similarity 0.70
Abstract

A graph class $\mathcal{C}$ is monadically dependent if one cannot interpret all graphs in vertex-colored graphs from $\mathcal{C}$ using a fixed formula of first-order logic. We prove that every monadically dependent graph class has almost bounded merge-width, thereby confirming a conjecture of the first and the last author [STOC '25]. Our proof is algorithmic and the witnessing decompositions in the form of merge sequences can be computed in nearly-cubic time. This is a step towards the proof of fixed-parameter tractability of model checking first-order logic on monadically dependent graph classes, which is achieved in a companion paper.

0.23

Dense Interprocedural Dominance in Acyclic Graphs: Context Bounds and Compact Queries

cs.DS ·2026-09-05 ·Peisen Yao
similarity 0.64
Abstract · We identified a substantive technical issue in the proof of the main theorem that affects several downstream results. Addressing the issue r…

Interprocedural dominance asks which program points every matched call-and-return execution must pass on its way to a target. An analysis that writes out immediate dominance pays for the transitive reduction of this order, the minimal dominator graph. Measured instances of that graph look near-linear, with edge-to-node ratios around 1.1--1.26~\cite{DeSutter2007}, but no program property is known to force this: it is unclear which structural restrictions imply sparse output, and whether dense output also rules out cheap queries. This paper answers both through calling contexts. A static node stands for the group of its reachable configurations; write $κ$ for the largest group size and $α$ for how many nodes have more than one configuration. One context per node keeps the tree with $n-1$ edges. Two already allow $Θ(n^2)$ cover edges in a sparse, loop-free, recursion-free ICFG with total degree three, constant-size procedures, and logarithmic stack depth, while the reachable configuration graph itself stays linear, so the blowup comes from grouping, not from many configurations. Three keep $Θ(n^2)$ covers even when the explicit call/return graph is acyclic: all target-reaching runs visit the mandatory procedures in the same order, and extra runs that stop short of any target remove the comparabilities that would otherwise kill the covers. Complementing the lower bounds, $α$ ambiguous nodes admit at most $\min\{\floor{n^2/4},(α+1)(n-1)\}$ cover edges, with $Ω(αn)$ attainable at stack depth one. And for every ICFG with at most two contexts per node, deleting a context group reduces dominance to dual-failure reachability, giving $O(n)$-word, $O(1)$-query representation after polynomial preprocessing. Explicit cover size, context ambiguity, and query-space cost are three separate quantities.

0.26

Robust Algebraic Theories of Triangle Graphs

cs.FL ·2026-08-11 ·Marius Bozga, Radu Iosif, Florian Zuleger
theory similarity 0.64
Abstract

Triangle graphs are graphs of tree-width at most three in which every edge belongs to a triangle. This class encompasses well-known graph families such as Apollonian networks. We also consider fan graphs, a subclass of triangle graphs closely related to the 3-connected triangle graphs. Our main result is an algebraic characterization of both classes. We introduce two graph algebras based on parallel composition and a ternary serial composition, and show that they generate exactly the triangle and fan graphs, respectively. These algebras provide a natural extension of the classical algebra of series-parallel graphs from tree-width two to tree-width three. Building on these characterizations, we investigate context-free, recognizable, and logically-definable graph languages. We show that counting monadic second-order logic (CMSO) is decidable over the context-free sets of triangle and fan graphs. Moreover, we prove that recognizable graph languages coincide with languages definable in CMSO for both algebras.

0.04

Width-Bounded Equational Derivations for Finite Graph Expressions

cs.LO ·2026-09-08 ·Antonios Kalampakas
theory similarity 0.63
Abstract · 71 pages. Includes complete supplementary proofs. Reproducibility package: https://doi.org/10.5281/zenodo.22297410

Completeness of an equational presentation guarantees an equality path but need not control the resources used along it. For finite graph expressions we measure derivational space by the largest input-output interface of an intermediate raw term. For every finite doubly ranked edge alphabet $Σ$, we prove that equal closed expressions of pattern width at most $k$ are joined by a derivation in which every step applies an equation in either direction and every intermediate width is at most a computable $B_Σ(k)$, independently of graph size. The derivation uses only the structural magmoid laws and the fifteen finite-graphoid schemes. The construction compiles each expression through protected cores and finite routing windows to an encoding-canonical representative $\operatorname{NF}_k$ of width at most $4k+4$. We call this property bounded equational coherence. We also prove $\operatorname{bw}(F)\le\operatorname{patw}(F)\le4(\operatorname{tw}(F)+1)$ whenever the underlying simple graph has at least two edges, separate layered linear from branching expressions on cliques, and provide machine-checkable witnesses and finite invariants for the first five nontrivial clique values.

0.28

Order-Invariant CFO Contains Local-Order-Invariant FO

cs.LO math.LO ·2026-11-01 ·Derek R. Aoki
similarity 0.63
Abstract · 19 pages

Order-invariant cluster first-order logic (CFO) and local-order-invariant first-order logic are two fragments of order-invariant first-order logic, both motivated by the study of invariant logics on classes of bounded degree. Our main result is that order-invariant CFO contains local-order-invariant FO on arbitrary classes of finite structures, settling the conjecture of Ghasemi and Grange that order-invariant CFO contains plain FO. By combining this with a collapse result of Ghasemi and Grange, we obtain the equivalence of FO, local-order-invariant FO, and order-invariant CFO on classes of finite colored graphs of bounded degree. The proof makes use of Gaifman normal form, which allows our translation from local-order-invariant FO to order-invariant CFO to be effective. Combined with the fixed-parameter tractability of model-checking for order-invariant CFO on bounded-degree colored graph classes, this shows that model-checking for local-order-invariant FO on bounded-degree colored graph classes is fixed-parameter tractable. To generalize our collapse and model-checking results beyond colored graphs, we use a method based on first-order interpretations which also yields a collapse of order-invariant FO to FO when restricted to graph classes of bounded shrub-depth. Finally, we give an application to the database-motivated frozen-witness logic of Abiteboul, Simon, and Vianu by showing that local-order-invariant FO contains deterministic frozen-witness FO, and thus that deterministic frozen-witness FO collapses to FO on classes of finite structures of bounded degree.

0.30

The (Parameterized) Complexity of Ordering a Graph While Avoiding a Forbidden Pattern

cs.DS cs.CC ·2026-08-31 ·Thomas Depian, Simon D. Fink, Alexander Firbas, Robert Ganian, Martin Nöllenburg +1 more
published similarity 0.63
Abstract · Appears in the Proceedings of the 21st International Symposium on Parameterized and Exact Computation (IPEC 2026); 57 pages, 11 figures, 1 t…

In this paper, we study the Pattern Avoidance problem of determining whether a given graph $G$ admits a linear vertex order which avoids a given pattern $P$, i.e., a vertex sequence with some forced and forbidden edges, on every suborder. Such patterns form a natural ordered counterpart to induced subgraphs in the order-invariant setting, and it is known that Pattern Avoidance captures a broad variety of graph problems including Bandwidth, Vertex Coloring, Queue Number, and extends to vertex-deletion problems such as Odd Cycle Transversal. We show that Pattern Avoidance is $Σ_2^{\textsf{P}}$-complete and furthermore remains intractable (in both the classical and parameterized sense) even under a variety of severe restrictions to both the pattern $P$ and the graph $G$. As our main contributions, we complement these lower bounds with the following tractability results, which provide a unifying framework for recognizing pattern-definable graph classes: - a fixed-parameter algorithm w.r.t. the vertex integrity of $G$ plus $|V(P)|$, - a fixed-parameter algorithm w.r.t. the neighborhood diversity of $G$ plus $|E(P)|$, and - a polynomial algorithm for Pattern Avoidance on forests for almost all constant-sized patterns.

0.54

A Fine-Grained Dichotomy for Bounded-Variable Query Evaluation: The Calculus of Relations, a Boolean Modal Logic, and One-Variable Counting Logic

cs.DB cs.CCcs.LO ·2026-10-03 ·Yoshiki Nakamura, Yuya Uezato
publishedtheory similarity 0.63
Abstract · Long version of PODS'27 paper

We study the fine-grained complexity of evaluating Boolean bounded-variable first-order queries over sparse relational structures. For every fixed $k \ge 2$, every relational signature, and every fragment between $k$-variable primitive positive ($\mathrm{PP}^{k}$) and first-order ($\mathrm{FO}^{k}$) logic, we prove, assuming the Sparse MAX-$3$-SAT hypothesis, a dichotomy theorem for evaluation in $O(m^{k-\varepsilon})$ time, where $m$ is the number of tuples in the input structure. The only tractable cases fall into three families: (1) three-variable fragments, (2) two-variable fragments, and (3) fragments over unary signatures. On the hard side, for every fixed $k \ge 4$ and every $\varepsilon > 0$, there is a fixed sentence $\varphi_\varepsilon$ in $\mathrm{PP}^{k}$ over a single binary relation symbol, depending on $\varepsilon$ but not on the input structure, whose evaluation cannot be performed in $O(m^{k-\varepsilon})$ time. For the tractable cases, we show that the evaluation problem can be solved in $2^{O(|\varphi|)} \cdot m^{k-\varepsilon}$ time for some $\varepsilon > 0$. Moreover, every tractable fragment reduces, with a $2^{O(|\varphi|)}$ blowup in formula size under DAG representations, to one of the following query languages: (1) Tarski's calculus of relations, (2) a new Boolean modal logic for sparse model checking, and (3) one-variable counting logic.

0.29