CS Paper Radar

Language-Representability: Possibilities and Limitations

Zhidan Feng, Henning Fernau, Pamela Fleischmann, Kevin Mann, Silas Cato Sacher

cs.FL ·submitted 2026-08-25 08:48 UTC · v1
published

Abstract

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.

Comment
In Proceedings AFL 2026, arXiv:2608.23071
Journal ref
EPTCS 451, 2026, pp. 155-170
DOI
10.4204/EPTCS.451.11

Closest papers

Nearest neighbours by meaning across the whole index.

Robust Algebraic Theories of Triangle Graphs

cs.FL ·2026-08-11 ·Marius Bozga, Radu Iosif, Florian Zuleger
theory similarity 0.68
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

Constrained intersection representations and forbidden patterns

cs.DM math.CO ·2026-11-12 ·Laurent Feuilloley, Michel Habib, Amalia Sorondo
similarity 0.67
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

Graph-based automata

cs.FL math.CO ·2026-09-08 ·Cyril Pujol
theory similarity 0.66
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

Lettericity Is NP-Complete

cs.CC cs.DM ·2026-09-23 ·Henning Fernau, Samuel German, Kevin Mann, Nils Morawietz
theory similarity 0.66
Abstract · After we first posted this paper on arXiv, Vatter posted a proof that Lettericity is NP-complete which he obtained independently of ours (ar…

The lettericity of a graph $G$ is the smallest size of a set $Σ$ such that there exist $w_1, \ldots, w_{|V(G)|} \in Σ$ and a so-called decoder $D \subseteq Σ^2$ for which $G$ is isomorphic to the letter graph $(\{1, \ldots, |V(G)|\}, \{ij : 1 \le i < j \le |V(G)|, w_iw_j \in D\})$. It took around two decades of the study of lettericity for, in the simpler case of paths, a closed-form expression for its lettericity to be derived; this suggests that the question of whether the lettericity of an arbitrary graph can be computed in polynomial time is nontrivial. Indeed, this question has been raised repeatedly as an open problem in recent literature. We solve this problem by showing that the lettericity problem on arbitrary graphs is NP-complete. We also show that each of the natural ways in which a single part of a structure $(Σ, w_1, \ldots, w_{|V(G)|}, D)$ witnessing the lettericity could be constrained corresponds to an NP-complete problem, which resolves an additional three open problems from the literature; in particular, we show that the coloring extension, word extension, and decoder extension problems are NP-complete. Additionally, we use the reduction in the NP-completeness proof to give a lower bound on algorithms for lettericity under the Exponential Time Hypothesis (ETH): unless the ETH is false, there cannot exist a deterministic algorithm to decide whether the lettericity of an $n$-vertex graph is at most $k$ in time $2^{o(n)}$, even when $n = 6k$. Finally, we complement the known result that Lettericity is fixed-parameter tractable when parameterized by the standard parameter $k$ by providing a fixed-parameter algorithm with respect to the dual parameterization by $n-k$ running in $2^{\mathcal{O}((n-k)^2)} + \mathcal{O}(n)$ time.

0.40

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

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

Pairwise Compatibility Graphs of Unweighted Caterpillars

cs.DM math.CO ·2026-10-10 ·Cyriac Antony, Manuel Lafond, Angelo Monti, Blerina Sinaimeri
similarity 0.60
Abstract

In this paper we study pairwise compatibility graphs whose witness tree is required to be an unweighted caterpillar. This is a natural restriction of PCGs, in the same line of research as the study of star witnesses, which led to the class of double-threshold graphs. In the caterpillar case, we show that this restriction is equivalent to a one-dimensional difference-labelling problem: a graph admits such a representation if and only if its vertices can be assigned integer labels so that adjacency is determined exactly by whether the absolute difference of two labels belongs to a given interval. Using this characterization, we derive structural properties of the class, including bounded twin-width, and study its relation with familiar graph families. We show that the class contains cycles and two-dimensional grids, while it excludes natural obstructions such as the subdivided star $S_{2,2,2,2,2}$, the cube graph $Q_3$, the wheel $W_6$, and the complement of the $3$-sunlet. We also consider restricted representations, including centipede witnesses and representations with a given interval and we give a polynomial-time recognition algorithm when the interval is fixed.

0.31

Every Regular Language Has a Bipartite Cactus Automaton

cs.FL ·2026-10-08 ·Mario Grobler, Till Koziel, Sebastian Siebertz
published similarity 0.60
Abstract · In Proceedings GandALF 2026, arXiv:2610.08898

Thompson's classical construction turns every regular expression into an equivalent epsilon-NFA whose transition graph is series-parallel. The construction uses epsilon-transitions, and eliminating them by the usual shortcut construction need not preserve planarity or the bound of two on the treewidth of the transition graph. Book and Chandra proved that every regular language nevertheless has an epsilon-free NFA with a planar transition graph. We show that the transition graph can in fact be chosen to be a bipartite cactus: every cycle is even, and any two cycles have at most one vertex in common. In particular, it is outerplanar and has treewidth at most two. This is a considerably more simple structure than the general series-parallel guarantee supplied by Thompson's construction. The proof is a direct induction on parity-typed regular expressions and uses only elementary closure properties of cactus graphs.

0.32