Polynomial instances of the positive semidefinite and Euclidean distance matrix completion problems

Given an undirected graph G = (V, E) with node set V = [1, n], a subset S s ubset of or equal to V, and a rational vector a is an element ofQ(S boolean ORE), the positive semidefinite matrix completion problem consists of dete rmining whether there exists a real symmetric n x n positive semidefinite m atrix X = (x(ij)) satisfying x(ii) = a(i) (i is an element of S) and x(ij) = a(ij) (ij is an element of E). Similarly, the Euclidean distance matrix c ompletion problem asks for the existence of a Euclidean distance matrix com pleting a partially defined given matrix. It is not known whether these pro blems belong to NP. We show here that they can be solved in polynomial time when restricted to the graphs having a fixed minimum fill-in,the minimum f ill-in of graph G being the minimum number of edges needed to be added to G in order to obtain a chordal graph. A simple combinatorial algorithm permi ts us to construct a completion in polynomial time n the chordal case. We a lso show that the completion problem is polynomially solvable for a class o f graphs including wheels of fixed length ( assuming all diagonal entries a re specified). The running time of our algorithms is polynomially bounded i n terms of n and the bitlength of the input a. We also observe that the mat rix completion problem can be solved in polynomial time n the real number m odel for the class of graphs containing no homeomorph of K-4.