Towards Settling the Complexity of the Lettericity Problem
For graph theorists and complexity theorists, this work clarifies the complexity boundaries of the lettericity problem, though the main problem remains open.
The authors investigate the computational complexity of the lettericity problem for graphs, showing that word retrieval and decoder retrieval are polynomial-time solvable, while coloring retrieval is equivalent to graph isomorphism. They also introduce symmetric lettericity, which equals neighborhood diversity and is computable in linear time.
The lettericity of a graph $G=(V,E)$ is defined as the smallest size of an alphabet $Σ$ such that there is a word $w_1 \dots w_{|V|} \in Σ^*$ and a decoder $\mathcal{D} \subseteq Σ^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 $χ\colon V(G) \rightarrow Σ$. 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 $χ$), 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.