Kevin Mann

Lettericity Is NP-Complete

The lettericity of a graph $G$ is the smallest size of a set $\Sigma$ such that there exist $w_1, \ldots, w_{|V(G)|} \in \Sigma$ and a so-called decoder $D \subseteq \Sigma^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 decad...