1998/11/01 by Benny Chor, Madhu Sudan · 6 citations
Computer Science · Mathematics · #Complexity and Algorithms in Graphs #Advanced Graph Theory Research #Computational Geometry and Mesh Generation #Betweenness centrality #Mathematics #Combinatorics #Discrete mathematics
paper · doi:10.1137/s0895480195296221
openalex publication_date 1998/11/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/06/11
An input to the betweenness problem contains m constraints over n real variables (points). Each constraint consists of three points, where one of the points is specified to lie inside the interval defined by the other two. The order of the other two points (i.e., which one is the largest and which one is the smallest) is not specified. This problem comes up in questions related to physical mapping in molecular biology. In 1979, Opatrny showed that the problem of deciding whether the n points can be totally ordered while satisfying the m betweenness constraints is NP-complete [SIAM J. Comput., 8 (1979), pp. 111--114]. Furthermore, the problem is MAX SNP complete, and for every α> 47/48 finding a total order that satisfies at least α of the m constraints is NP-hard (even if all the constraints are satisfiable). It is easy to find an ordering of the points that satisfies 1/3 of the m constraints (e.g., by choosing the ordering at random). This paper presents a polynomial time algorithm that either determines that there is no feasible solution or finds a total order that satisfies at least 1/2 of the m constraints. The algorithm translates the problem into a set of quadratic inequalities and solves a semidefinite relaxation of them in \cal Rn. The n solution points are then projected on a random line through the origin. The claimed performance guarantee is shown using simple geometric properties of the semidefinite programming (SDP) solution.