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 equivalent to the NP-hard problem of computing the intersection number of G , thus in turn equivalent to the clique cover problem. We describe a heuristic algorithm that computes an approximation to Σ min and a corresponding x . We give various properties of our algorithm, including some experimental evidence that on average it requires O ( n 2 log ⁡ n ) time. We compare it with other heuristics, and state some conjectures and open problems.