Lettericity Is NP-Complete

Henning Fernau, Samuel German, Kevin Mann +1

The lettericity of a graph $G$ is the smallest size of a set $\Sigma$ such that there exist $w_1,\dots ,w_{|V(G)|}\in \Sigma$ and a so-called decoder $D\subseteq {\Sigma }^2$ for which $G$ is is…