arxiv: 2605.07899 · v1 · submitted 2026-05-08 · 💻 cs.DS

Recognition: no theorem link

Towards Settling the Complexity of the Lettericity Problem

Mario Grobler , Nils Morawietz , Silas Cato Sacher

Authors on Pith no claims yet

Pith reviewed 2026-05-11 03:29 UTC · model grok-4.3

classification 💻 cs.DS

keywords lettericityletter graphsretrieval problemsneighborhood diversitygraph isomorphismpolynomial-time algorithmssymmetric decoders

0 comments

The pith

Word and decoder retrieval for lettericity are solvable in polynomial time, while coloring retrieval is equivalent to graph isomorphism.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper examines the lettericity of a graph, defined as the smallest alphabet size permitting a word and decoder such that the graph arises exactly as the letter graph with edges dictated by decoder pairs. It proves that recovering the missing word or decoder, when the graph and one of the other two objects are supplied, can be done efficiently. Recovering the coloring instead turns out to require solving graph isomorphism in both directions. The authors further introduce symmetric lettericity, requiring the decoder to treat ordered pairs symmetrically, and establish that this quantity is identical to the neighborhood diversity of the graph and therefore computable in linear time.

Core claim

Lettericity of G is the minimal size of an alphabet Sigma together with a word w over Sigma and decoder D subset of Sigma squared such that G is isomorphic to the graph on positions 1 to n with an edge ij whenever wi wj belongs to D. Given G and w, the decoder D can be recovered in polynomial time; given G and D, the word w can likewise be recovered in polynomial time. Given G and either w or D, recovering the implied coloring chi is polynomial-time equivalent to deciding whether two graphs are isomorphic. Symmetric lettericity, the variant in which D must satisfy ab in D if and only if ba in D, equals the neighborhood diversity of G and is therefore computable in linear time.

What carries the argument

The letter graph G(D, w) on vertex set {1,...,n} whose edges are exactly the pairs ij (i<j) for which wi wj lies in the decoder D; the three retrieval tasks that supply the graph plus any two of {word, decoder, coloring} and ask for the remaining one; the symmetric decoder restriction and its equality to neighborhood diversity.

If this is right

Word retrieval and decoder retrieval each admit polynomial-time algorithms when the graph and the complementary object are provided.
Coloring retrieval is polynomial-time equivalent to the graph isomorphism problem.
Symmetric lettericity is identical to neighborhood diversity for every graph.
Symmetric lettericity can be computed in linear time for any input graph.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The polynomial-time retrieval procedures may serve as subroutines inside a search for minimal-lettericity representations.
Because coloring retrieval inherits the exact complexity of graph isomorphism, any future proof that lettericity itself lies in P would have to circumvent or absorb the isomorphism-equivalence obstacle.
The linear-time computability of symmetric lettericity supplies an efficiently obtainable lower or upper bound on ordinary lettericity for every graph.

Load-bearing premise

The letter graph model with its word, decoder, and coloring objects is formalized without hidden constraints, and the claimed polynomial-time procedures and equivalence reductions hold under the standard model of computation.

What would settle it

A concrete graph G together with a word w for which any claimed polynomial-time decoder-retrieval procedure outputs a decoder D that fails to reproduce exactly the edge set of G, or a pair of non-isomorphic graphs on which the coloring-retrieval procedure distinguishes them differently from an isomorphism test.

Figures

Figures reproduced from arXiv: 2605.07899 by Mario Grobler, Nils Morawietz, Silas Cato Sacher.

**Figure 1.** Figure 1: An example for the transformation of the Word Retrieval-instance to a directed graph. Here, a vertex ci implies that this vertex receives color c under the labeling χ. The solid arcs are added due to Condition (i) of the definition of the arc set and the single dashed arc is added due to Condition (ii). The unique topological ordering b1a1n1a2n2e1 of this example graph is the unique generalized solution fo… view at source ↗

**Figure 2.** Figure 2: An example for a word w that is not a palindrome and the decoder can only contain one of the words ab or ba. The word w starts and ends with a-runs of same length (namely, length 1), so there needs to be a vertex in Va that is adjacent to all vertices of Vb, and there needs to be a vertex in Va that has no neighbor in Vb. These vertices are a1 and a3, respectively. To derive the unique decoder word for D, … view at source ↗

**Figure 3.** Figure 3: An example for a word w where {a, b} and {b, c} are one-sided letter pairs, w[a, b] and w[b, c] contain at least two b-runs each, and where w[b, c] is a palindrome. The choice for the word of {bc, cb} for the decoder is determined by the choice for the word of {ab, bc} for the decoder. Note that the latter is fixed, as w[a, b] is not a palindrome. Namely, for each decoder D which is a solution, we need to … view at source ↗

read the original abstract

The lettericity of a graph $G=(V,E)$ is defined as the smallest size of an alphabet $\Sigma$ such that there is a word $w_1 \dots w_{|V|} \in \Sigma^*$ and a decoder $\mathcal{D} \subseteq \Sigma^2$ with the property that $G$ is isomorphic to the letter graph $G(\mathcal{D}, w)$, that is, the graph with vertex set $\{1, \dots, n\}$ and edge set $\{ij \mid 1\leq i < j \leq n, w_iw_j \in \mathcal{D}\}$. Note that $G(\mathcal{D}, w)$ can be seen as a graph with inherent coloring $\chi \colon V(G) \rightarrow \Sigma$. It is unknown whether the lettericity of a given graph can be computed in polynomial time. The problem to determine the lettericity of a given graph is called the lettericity problem. As a step towards answering the complexity of this problem, we investigate the following retrieval problems: given a graph $G$ together with two of the three solution-objects (word $w$, decoder $\mathcal{D}$, and coloring $\chi$), the goal is to compute the third solution-object. We show that word retrieval and decoder retrieval are solvable in polynomial time, while coloring retrieval is equivalent to the graph isomorphism problem. Beyond this, we introduce symmetric lettericity which is a restricted version of lettericity where each decoder needs to be symmetrical ($ab\in \mathcal{D}$ if and only if $ba\in \mathcal{D}$). As we show, the symmetric lettericity of a graph always equals the neighborhood diversity of the graph, which in fact can be computed in linear time.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper classifies three retrieval problems for letter graphs as P or GI-equivalent and shows symmetric lettericity equals neighborhood diversity.

read the letter

The main points are that word retrieval and decoder retrieval can be done in polynomial time, coloring retrieval is equivalent to graph isomorphism, and symmetric lettericity is exactly neighborhood diversity, which is already linear-time computable. These are the concrete results the authors deliver as steps toward the open lettericity problem. They define the three retrieval problems cleanly and prove the stated complexities plus the equivalence. The poly-time algorithms give explicit ways to recover the missing object when two are provided, and the symmetric case collapses directly to a known parameter. This is new material; the retrieval variants and the exact equivalence do not appear in the cited prior work on letter graphs. The paper does well by sticking to standard complexity techniques and avoiding overclaims about the main open question. The soft spots are limited. The full lettericity problem itself stays unresolved, so the advance is incremental rather than decisive. The GI equivalence for coloring retrieval follows from the labeling interpretation, but the exact reduction would need checking for edge cases around alphabet size or non-unique decoders. The linear-time claim for neighborhood diversity is standard and not a new contribution here. This work is for researchers in algorithmic graph theory who track parameters like lettericity or neighborhood diversity. A reader focused on complexity classifications of representation problems gets the most value. It deserves a serious referee because the claims are well-motivated, the techniques are appropriate, and the results are falsifiable. I would send it to peer review.

Referee Report

0 major / 3 minor

Summary. The manuscript defines the lettericity of a graph G as the smallest alphabet size |Σ| admitting a word w ∈ Σ^n and decoder D ⊆ Σ² such that G is isomorphic to the letter graph G(D, w) whose edges are determined by pairs in D. It studies three retrieval problems (recover the missing object among w, D, and the induced coloring χ : V → Σ) and proves that word retrieval and decoder retrieval are solvable in polynomial time while coloring retrieval is polynomial-time equivalent to graph isomorphism. It further introduces symmetric lettericity (requiring D to be symmetric) and shows that this parameter equals the neighborhood diversity of G, which is computable in linear time.

Significance. If the algorithmic claims and reductions hold, the paper supplies a useful partial classification of the lettericity problem: two of the three natural retrieval variants are tractable, one is GI-hard, and the symmetric restriction collapses to a known linear-time parameter. The explicit connection between symmetric lettericity and neighborhood diversity, together with the polynomial-time retrieval algorithms, gives concrete algorithmic tools and clarifies the boundary between easy and hard cases in this model.

minor comments (3)

[§3] §3 (Word Retrieval): the running-time analysis of the algorithm that recovers w from G and D should state the precise degree of the polynomial (e.g., O(n²) or O(n³)) rather than only “polynomial time.”
[§5] §5 (Symmetric Lettericity): the proof that symmetric lettericity equals neighborhood diversity relies on grouping vertices by identical neighborhoods; a short remark confirming that this grouping can be performed in linear time via adjacency-list sorting or hashing would strengthen the claim.
[Abstract / §1] The abstract and introduction use “coloring retrieval” without an explicit forward reference to the section that defines the coloring χ induced by the word; adding such a pointer would improve readability.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive summary, significance assessment, and recommendation of minor revision. The referee's description of the manuscript is accurate. No major comments were raised in the report.

Circularity Check

0 steps flagged

No significant circularity in the derivation chain

full rationale

The paper explicitly defines lettericity via the letter graph G(D, w) and introduces the three retrieval problems without hidden constraints or self-referential loops. It then supplies direct algorithmic constructions showing word and decoder retrieval are in P, reduces coloring retrieval to graph isomorphism via explicit equivalence, and proves symmetric lettericity equals neighborhood diversity by relating the symmetric decoder to neighborhood signatures, which is independently known to admit linear-time computation. None of these steps reduce by construction to fitted inputs, self-citations, or renamed ansatzes; the results rest on standard reductions and explicit algorithms that remain falsifiable against external graph-theoretic benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 3 axioms · 0 invented entities

The work relies entirely on standard graph theory and complexity definitions with no free parameters, new entities, or ad-hoc axioms introduced to support the claims.

axioms (3)

standard math Graphs are finite, undirected, and simple.
Standard background assumption for all graph problems in the paper.
standard math Polynomial time is defined with respect to the standard multi-tape Turing machine model.
Used to classify the retrieval algorithms.
standard math Graph isomorphism is the decision problem of determining whether two graphs are isomorphic.
Central to the coloring retrieval equivalence claim.

pith-pipeline@v0.9.0 · 5619 in / 1364 out tokens · 67403 ms · 2026-05-11T03:29:09.658356+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

14 extracted references · 14 canonical work pages

[1]

SIAM Journal on Discrete Mathematics36(4), 2774–2797 (2022)

Alecu, B., Ferguson, R., Kanté, M.M., Lozin, V.V., Vatter, V., Zamaraev, V.: Letter graphs and geometric grid classes of permutations. SIAM Journal on Discrete Mathematics36(4), 2774–2797 (2022)

work page 2022
[2]

Algorithmica88(1), 2 (2026) Towards Settling the Complexity of the Lettericity Problem 17

Alecu, B., Kanté, M.M., Lozin, V.V., Zamaraev, V.: Lettericity of graphs: an FPT algorithm and a bound on the size of obstructions. Algorithmica88(1), 2 (2026) Towards Settling the Complexity of the Lettericity Problem 17

work page 2026
[3]

CoRR abs/2106.03267(2021).https://doi.org/10.48550/ARXIV.2106.03267

Alecu, B., Lozin, V.: Understanding lettericity I: a structural hierarchy. CoRR abs/2106.03267(2021).https://doi.org/10.48550/ARXIV.2106.03267

work page doi:10.48550/arxiv.2106.03267 2021
[4]

Discrete Mathematics338(2), 164–179 (2015)

Atminas, A., Collins, A., Lozin, V.V., Zamaraev, V.: Implicit representations and factorial properties of graphs. Discrete Mathematics338(2), 164–179 (2015)

work page 2015
[5]

Mathematics in Computer Science10(2), 209–222 (2016)

Bera, S., Mahalingam, K.: Structural properties of word representable graphs. Mathematics in Computer Science10(2), 209–222 (2016)

work page 2016
[6]

Discrete Applied Mathematics261, 78–92 (2019)

Bonomo, F., de Estrada, D.: On the thinness and proper thinness of a graph. Discrete Applied Mathematics261, 78–92 (2019)

work page 2019
[7]

CoRRabs/2602.24064(2026)

Feng, Z., Fernau, H., Fleischmann, P., Kindermann, P., Sacher, S.C.: Determining factorial speed fast. CoRRabs/2602.24064(2026). https://doi.org/10.48550/ ARXIV.2602.24064

work page arXiv 2026
[8]

In: Procedings of the 11th Algorithms and Discrete Applied Mathematics (CALDAM ’25)

Feng, Z., Fernau, H., Mann, K., Raman, I., Sacher, S.C.: Generalized Lettericity of Graphs. In: Procedings of the 11th Algorithms and Discrete Applied Mathematics (CALDAM ’25). pp. 134–146. Lecture Notes in Computer Science, Springer (2025)

work page 2025
[9]

Australasian Journal of Combinatorics 78, 348–351 (2020)

Ferguson, R.: On the lettericity of paths. Australasian Journal of Combinatorics 78, 348–351 (2020)

work page 2020
[10]

Discrete Applied Mathematics309, 215–220 (2022)

Ferguson, R., Vatter, V.: Letter graphs and modular decomposition. Discrete Applied Mathematics309, 215–220 (2022)

work page 2022
[11]

Electronic Journal of Combinatorics31(4) (2024)

Mandrick, S., Vatter, V.: Bounds on the lettericity of graphs. Electronic Journal of Combinatorics31(4) (2024)

work page 2024
[12]

Universit’a di Roma La Sapienza, Dipartimento di Informatica e Sistemistica26(02) (2002)

Mannino, C., Oriolo, G., Ricci, F.: Solving stability problems on a superclass of interval graphs. Universit’a di Roma La Sapienza, Dipartimento di Informatica e Sistemistica26(02) (2002)

work page 2002
[13]

Discrete Mathematics244(1-3), 375–388 (2002)

Petkovsek, M.: Letter graphs and well-quasi-order by induced subgraphs. Discrete Mathematics244(1-3), 375–388 (2002)

work page 2002
[14]

Pacific Journal of Mathematics339(2), 333–343 (2025)

Shitov, Y.: Graph thinness: a lower bound and complexity. Pacific Journal of Mathematics339(2), 333–343 (2025)

work page 2025