CS Paper Radar

Robust Algebraic Theories of Triangle Graphs

Marius Bozga, Radu Iosif, Florian Zuleger

cs.FL ·submitted 2026-08-11 13:57 UTC · v2
theory

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.

Closest papers

Nearest neighbours by meaning across the whole index.

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

Language-Representability: Possibilities and Limitations

cs.FL ·2026-08-25 ·Zhidan Feng, Henning Fernau, Pamela Fleischmann, Kevin Mann, Silas Cato Sacher
published similarity 0.68
Abstract · In Proceedings AFL 2026, arXiv:2608.23071

The study of word-representability was initiated by the seminal work of Kitaev and Pyatkin in 2008 that has later led to the monograph by Kitaev and Lozin in 2015. In this paper, we build on the very recent work by Fernau et al. who proposed a general framework that generalizes certain aspects of word-representability, so that any binary language describes a graph class. In this work, we systematically study particularly small languages and observe that they characterize well-known graph classes, e.g., interval, permutation, circle, and bipartite chain graphs. Thus, we strengthen the bond between formal languages and graph classes, even for small binary languages. We also show some limitations of our approach by proving that, e.g., families of sparse graphs like planar graphs cannot be characterized by any language following this approach.

0.37

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.68
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

Extensions of Courcelle's Theorem without Logic

cs.LO ·2026-08-21 ·Yuval Filmus, Johann A. Makowsky
theory similarity 0.67
Abstract · 17 pages. This is an expanded and improved version of arXiv:2505.02771

Courcelle's Theorem states that on graphs $G$ of tree-width at most $k$ with a given tree-decomposition of size $t(G)$, graph properties $\mathcal{P}$ definable in Monadic Second Order Logic can be checked in linear time in the size of $t(G)$. Inspired by L. Lovász' work using connection matrices instead of logic, we give a generalized version of Courcelle's theorem which replaces the definability hypothesis by a purely combinatorial hypothesis using a generalization of connection matrices. This paper clarifies the role of logic in such theorems and displays their purely combinatorial assumption.

0.18

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

cs.LO cs.DMmath.LO ·2026-10-04 ·Nikolas Mählmann, Patrice {Ossona de Mendez}, Nicole Schirrmacher, Sebastian Siebertz, Giannos Stamoulis +2 more
similarity 0.64
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.

0.16

Graph-based automata

cs.FL math.CO ·2026-09-08 ·Cyril Pujol
theory similarity 0.64
Abstract

We study graph-based automata: nondeterministic finite automata obtained from edge-colored or oriented graphs by taking every vertex as both initial and accepting, and every edge as a pair of opposite transitions. The language of these automata corresponds to the set of edge-colored or oriented paths mapping to their corresponding graphs. We develop an analogous notion for trees and characterise the languages recognised by these models. For tree languages we prove the existence of a unique size- minimal graph and, more generally, a homomorphism-minimal graph for both word and tree languages using duality methods. In order to further motivate these models, we showcase a few results at the inter- section between graph theory and automata theory: We relate graph-based automata to reversible automata, give a decomposition of graph-based languages into reversible languages, and introduce the remanent language of an undirected graph as the inter- section of all its orientations. This remanent language captures structural information on the graph such as chromatic number.

0.19

Constrained intersection representations and forbidden patterns

cs.DM math.CO ·2026-11-12 ·Laurent Feuilloley, Michel Habib, Amalia Sorondo
similarity 0.63
Abstract

We study the interplay between two types of graph classes: the ones defined by intersections of geometric objects and the ones defined by the absence of a substructure. More precisely, we study intersection graphs that are grounded, that is, the objects lie above a horizontal line that they touch, and ordered graphs with forbidden patterns, that is, ordered graphs that avoid a set of ordered induced subgraphs. These two approaches are fundamentally different, but it is known that several interesting graph classes have both types of characterizations, and we aim to understand whether this is a general phenomenon. Our contributions are the following. First, we identify a family of patterns on four vertices and a natural hierarchy of intersection graphs of strings whose classes are nicely interleaved. This raises hopes to prove connections between the two perspectives. Second, we dampen these hopes by proving that a class of (ordered) intersection graphs that we study cannot be characterized by a finite set of forbidden patterns. Third, we show a dual impossibility result: there exists a pattern-defined class of our hierarchy that admits no intersection representation, if we require this representation to be closed under natural operations such as translation and scaling. However, it turns out that if we allow slightly more exotic intersection representations, then we can find one for this pattern-defined class.

0.30

Flip-packability: uniform characterisations of tame graph classes

cs.LO cs.DMmath.COmath.LO ·2026-09-27 ·Ioannis Eleftheriadis
theory similarity 0.62
Abstract · 32 pages; added funding information

A class of graphs is monadically dependent if one cannot encode all graphs in coloured graphs from the class using a fixed first-order formula, and monadically stable if one cannot even encode arbitrarily long linear orders. Bonnet et al. (ICALP 2025) characterised monadic dependence by flip-separability: for every vertex weighting, boundedly many flips - complementations of the adjacency relation within a vertex subset - make every ball of radius $r$ carry at most an $\varepsilon$-fraction of the weight, so that every set carrying an $\varepsilon$-fraction has two elements pulled apart. We introduce flip-packability: boundedly many graphs, each obtained from the input by boundedly many flips and all determined by the weighting before any set is presented, such that every set carrying an $\varepsilon$-fraction of the weight has $m$ elements pairwise far apart in one of them. The number of flips producing each graph depends on the radius alone; only the number of graphs depends on $\varepsilon$ and $m$. We prove that a class of graphs is flip-packable if and only if it is monadically stable, and $2$-flip-packable, that is, flip-packable with $m=2$, if and only if it is monadically dependent. The passage from two scattered elements to $m$ is thus exactly what separates the two notions. For monadically stable classes we show that the flipped graphs can be computed from the weighting in cubic time. Varying the three parameters of the definition - the sparsifying operation, the radius, and the number $m$ of elements scattered - produces eight known characterisations of sparse and dense graph classes from the same template. In each case $m$ separates a depth-like notion from its width-like relaxation: treedepth from treewidth, shrubdepth from cliquewidth, and monadic stability from monadic dependence.

0.24