A Note on Discretization Orders for Distance Geometry Problems

When a weighted graph is an instance of the Distance Geometry Problem, certain types of vertex orders (called discretization orders) make it amenable to be solved by means of a discrete search type algorithm, rather than a continuous one. We show that finding a discretization order is difficult if we require each vertex to be adjacent to immediate predecessors (which happens to be the case for the important application to finding the 3D structure of proteins). This justifies the use of heuristics in finding such orders.