Chapter 32Distance Geometry: NP-Hard, NP-Hard to Approximate
NMR spectroscopy exploiting the nuclear Overhauser effect (NOE) gives us a way to measure distances between atoms. This is very handy: Given all the distances between every pair of atoms in a protein, it should, in theory, be possible to reconstruct the protein’s structure. However, NOEs are both noisy and sparse. As a result, it is computationally difficult to produce a structural model of a protein, from NOE data alone. In fact, as Saxe [1] proves, it is NP-complete to do so (if you solve this problem, you solve every other NP problem), and NP-complete to even approximate it.
What does this mean? It means that there should be no provably fast way to solve the problem we know as distance geometry, which Saxe [1] refers to as “k-embeddability.” The application to protein structure determination is obvious. And given that this problem is proven to be NP-complete to solve and even to approximate, algorithms attempting to solve for distance geometry are provably unable to provide both reasonably fast, and provably good results. As a result, researchers in the field have developed either provably good but slow algorithms, or reasonably fast but not provably accurate algorithms.
Saxe’s results [1] do not mean that heuristic, stochastic approaches such as simulated annealing/molecular dynamics (SA/MD) cannot run quickly or compute accurate structures. But it does say that these NOE-based approaches cannot be proven to do so. On the other hand, we have seen that RDC-based algorithms enjoy guarantees of efficiency, soundness, and completeness that are forbidden to NP-hard problems such as distance geometry (chapters 15–18). This is because RDCs are global, while NOEs are local.
Introduction
Review: Reductions
A Nondeterministic Polynomial-time (NP) problem is a problem that, given a solution together with sufficient support, can be verified in polynomial time. Problems that are NP-hard are believed to be harder than all the other NP problems.
The basic idea behind a reduction is the ability to show that, given a problem of one form (usually that of an NP-hard problem), we can efficiently convert it into a problem of the form we want to prove is NP-hard, and the solution to the new form can be transferred back. If we can do this in polynomial time, and the transformed problem is in P, then we’ve just developed a solution for a nonpolynomial time problem whose time complexity is merely the sum of two polynomials, which is still a polynomial! The idea is that “if you can solve this problem in polynomial time, you can solve an NP-hard problem in polynomial time as well!”
The implications of any such proof are obvious: Unless a polynomial-time solution for an NP-complete problem exists (and none have been found yet), any problem that can be proved to be NP-complete can thus be considered intractable, in the sense that unless , no polynomial-time solution exists. There is much evidence that .
NP-Hard Problems
In his paper [1], J. B. Saxe reduces two different problems, named Partition and 3SAT, to the problem of distance geometry (which he refers to as ” -embeddability”).
To describe the problems, as Saxe defines them:
Partition: Given a set of integers, can it be divided into two subsets such that their sums are equal?
3SAT: Given an expression in first-order logic, is there a set of Boolean variable assignments that makes the expression evaluate to true?
-embeddability: Given a graph , where assigns each edge in a weight, is there a function that assigns integer positions to every vertex in into -dimensional space such that for every edge , ?
Reduction from Partition to 1-Embeddability
Given any set of integers , a cycle of vertices such that each edge has weight can be constructed in linear time. If this cycle is embeddable in 1 dimension, all edges where can be grouped into one set and all edges where can be grouped into the other set, such that the two sets have an equal sum. This is because, when traversing the vertices of a cycle, the first vertex visited is returned to, by definition of a cycle. The implication of this is that any distance traveled in one direction must be traveled back, to return to the starting vertex’s assigned location.
Reduction from 3SAT to 1-Embeddability
Using edge lengths of only 1 and 2, Saxe shows that it is possible to construct a graph for which the output (if there is any function for which the graph becomes embeddable in one dimension) corresponds to the logical truth value of whether an expression can be satisfied. See figures 32.1 and 32.2.
Figure 32.1 Representing variables and clauses in 1-embeddable graphs. (a) Implementation of variables; (b) implementation of a negative literal. Variables can only be assigned values of , which corresponds with the true/false values of 3SAT variables [1].
Figure 32.2 The gadget to implement a disjunctive 3SAT clause. On inspection one can confirm that at least one of the three variables in the graph must be assigned to for there to exist a function that can embed the graph into one dimension [1].
Reduction from 3SAT to Integer 1-Embeddability
Up to this point, Saxe only shows that to embed graphs of edge weights is NP-hard. With the use of these two gadgets, however, embedding any graph of lengths can be shown to be NP-hard, and, inductively, any integer-weighted graph can be broken down until it consists entirely of edge lengths (see figure 32.3). Thus, he shows that the 1-embeddability of any integer-weighted graph is NP-hard.
Adding Dimensions
By introducing two more gadgets, Saxe shows that it is possible to convert a graph that is embeddable in 1 dimension into a graph that must be embedded in two dimensions; in his words, he “adds a dimension” to the graph (see figure 32.4). To move the graph into additional dimensions, other gadgets could be used as well.
Approximation
Definition of -Approximate -Embeddability
A graph is said to be -approximately -embeddable if there exists a function such that for all vertices , .
Figure 32.3 By replacing all edges of length 3 and all edges of length 4 with the gadgets shown above, all graphs can be reduced to edge-weighted graphs [1].
Figure 32.4 By replacing all edges of length 1 and all edges of length 2 with the gadgets R1 and R2, respectively, any 1-dimensional graph can be converted into a graph that is representable in only 2 or 3 dimensions. It is left to the reader to contrive gadgets for additional dimensions if so desired [1].
Saxe shows the reduction of 3SAT to real number edge-weighted embeddability. He observes that the gadget used to reduce 1-embeddability relies only on cycles of length no greater than 16. From this, it follows that the total distance traveled from any point in that cycle can be no longer than , and therefore for any real number , the resulting embeddability problem is equivalent to exact integral -embeddability. As a result of this, he claims that given any -approximate -embeddability problem, there exists a rational number such that for all , the problem reduces intrinsically to the exact -embeddability of that graph, and is thus NP-hard as well.
Reference
- [1] J. B., Saxe. Embeddability of weighted graphs in -space is strongly NP-hard. Proceedings of the 17th Allerton Conference on Communications, Control, and Computing, (1979): 480–489.