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⊆ V, and a rational vector a∈ QS∪ E, the positive semidefinite matrix completion problem consists of determining whether there exists a real symmetric n × n positive semidefinite matrix X=(x ij ) satisfying x ii =a i (i∈ S) and x ij =a ij (ij∈ E). Similarly, the Euclidean distance matrix completion problem asks for the existence of a Euclidean distance matrix completing a partially defined given matrix. It is not known whether these problems 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 fill-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 permits us to construct a completion in polynomial time in the chordal case. We also show that the completion problem is polynomially solvable for a class of graphs including wheels of fixed length (assuming all diagonal entries are specified). The running time of our algorithms is polynomially bounded in terms of n and the bitlength of the input a. We also observe that the matrix completion problem can be solved in polynomial time in the real number model for the class of graphs containing no homeomorph K 4 .