Constructing an indeterminate string from its associated graph

As discussed at length in Christodoulakis et al. (2015) [3], there is a natural one-many correspondence between simple undirected graphs G with vertex set V = { 1 , 2 , … , n } and indeterminate strings x = x [ 1 . . n ] — that is, sequences of subsets of some alphabet Σ. In this paper, given G , we consider the “reverse engineering” problem of computing a corresponding x on an alphabet Σ min of minimum cardinality. This turns out to be …