The sensor network localization, SNL, problem in embedding dimension r, consists of locating the positions of wireless sensors, given only the distances between sensors that are within radio range and the positions of a subset of the sensors (called anchors). Current solution techniques relax this problem to a weighted, nearest, (positive) semidefinite programming, SDP, completion problem, by using the linear mapping between Euclidean distance matrices, EDM, and semidefinite matrices. The resulting SDP is solved using primal-dual interior point solvers, yielding an expensive and inexact solution. This relaxation is highly degenerate in the sense that the feasible set is restricted to a low dimensional face of the SDP cone, implying that the Slater constraint qualification fails. Cliques in the graph of the SNL problem give rise to this degeneracy in the SDP relaxation. In this paper, we take advantage of the absence of the Slater constraint qualification and derive a technique for the SNL problem, with exact data, that explicitly solves the corresponding rank restricted SDP problem. No SDP solvers are used. For randomly generated instances, we are able to efficiently solve many huge instances of this NP-hard problem to high accuracy, by finding a representation of the minimal face of the SDP cone that contains the SDP matrix representation of the EDM. The main work of our algorithm consists in repeatedly finding the intersection of subspaces that represent the faces of the SDP cone that correspond to cliques of the SNL problem.
@cite_31: The graph realization problem is that of computing the relative locations of a set of vertices placed in Euclidean space, relying only upon some set of inter-vertex distance measurements. This paper is concerned with the closely related problem of determining whether or not a graph has a unique realization. Both these problems are NP-hard, but the proofs rely upon special combinations of edge lengths. If one assumes the vertex locations are unrelated, then the uniqueness question can be approached from a purely graph theoretic angle that ignores edge lengths. This paper identifies three necessary graph theoretic conditions for a graph to have a unique realization in any dimension. Efficient sequential and NC algorithms are presented for each condition, although these algorithms have very different flavors in different dimensions.
@cite_1: Alon, Krivelevich, and Sudakov [Random Struct Algorithms 13(3–4) (1998), 457–466.] designed an algorithm based on spectral techniques that almost surely finds a clique of size hidden in an otherwise random graph. We show that a different algorithm, based on the Lovasz theta function, almost surely both finds the hidden clique and certifies its optimality. Our algorithm has an additional advantage of being more robust: it also works in a semirandom hidden clique model, in which an adversary can remove edges from the random portion of the graph. ©2000 John Wiley & Sons, Inc. Random Struct. Alg., 16, 195–208, 2000
@cite_15: The molecule problem is that of determining the coordinates of a set of points in space from a (usually sparse) set of pairwise distance measurements. As its name implies, it has applications in the determination of molecular conformation. Unfortunately, the molecule problem is NP-hard. We present an approach to the molecule problem that uses a very specialized divide-and-conquer technique. Instead of solving a single large problem we try to solve a sequence of smaller, presumably easier ones. These smaller problems consist of subsets of points whose relative locations can be determined uniquely. Once such a subset is positioned, its points can collectively be treated as a rigid body. This can greatly reduce the number of degrees of freedom in the problem. Identifying subsets of points whose relative locations can be uniquely determined requires exploiting some very special structure inherent in the molecule problem. We reduce this identification to a purely combinatoric characterization that ignores the actual distances. We develop necessary graph theoretic conditions for a set of points to have a unique solution, along with efficient algorithms to find subgraphs with these properties. These characterizations and algorithms combine ideas from matching theory, differential topology and matrix computations. These ideas have been implemented in ABBIE, a program to solve three-dimensional instances of the molecule problem. ABBIE combines the recursive decomposition described above with a nonlinear global optimizer to perform the coordinate determinations. Details of this implementation are described, and numerical results of simulated chemical data are presented.
@cite_16: We consider the problems of finding a maximum clique in a graph and finding a maximum-edge biclique in a bipartite graph. Both problems are NP-hard. We write both problems as matrix-rank minimization and then relax them using the nuclear norm. This technique, which may be regarded as a generalization of compressive sensing, has recently been shown to be an effective way to solve rank optimization problems. In the special cases that the input graph has a planted clique or biclique (i.e., a single large clique or biclique plus diversionary edges), our algorithm successfully provides an exact solution to the original instance. For each problem, we provide two analyses of when our algorithm succeeds. In the first analysis, the diversionary edges are placed by an adversary. In the second, they are placed at random. In the case of random edges for the planted clique problem, we obtain the same bound as Alon, Krivelevich and Sudakov as well as Feige and Krauthgamer, but we use different techniques.
@cite_11: 
The problem with given embedding dimension @math is NP-hard embedding dimension, @math @cite_15 @cite_31 @cite_11 . However, from our numerical tests it appears that random problems that have a unique solution can be solved very efficiently. This phenomenon fits into the results in @cite_16 @cite_1 .