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.

Authors

• Joel Helling
• P.J. Ryan
• W.F. Smyth
• Michael Soltys

Keywords

• String algorithms
• Indeterminate strings
• Cliques
• Graph labeling