An impossible combinatorial counting method in distance geometry

The Distance Geometry Problem asks for a geometric representation of a given weighted graph in R^K so that vertices are points and edges are segments with lengths equal to the corresponding weights. Two problem variants are defined by a vertex order given as part of the input, which allows the use of a branching algorithm based on K-lateration: find two possible positions for the next vertex j using the positions of K predecessors and their distances to j, then explore each position recursively, pruning positions at need. Whereas the first variant only requires the K predecessors to exist, the second variant also requires them to be contiguous and immediately preceding j. For this variant, fixed-parameter tractability of the algorithm can be established by means of a solution counting method that only depends on the graph edges (rather than their weights). Only in the first variant, however, it is possible to efficiently construct a suitable vertex order directly from the graph. Since both fixed-parameter tractability and efficient vertex order construction are desirable properties, one would need an analogous solution counting method for the first variant. In this paper we prove that such a counting method cannot be devised for the first variant.