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\subseteq V$, and a rational vector $a\in {\rm\bf Q}^{S\cup E}$, the positive semidefinite  matrix completion problem consists of determining whether there exists a real symmetric n  n positive semidefinite matrix X=(xij) satisfying xii=ai ($i\in S$) and xij=aij ($ij\in 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 K4.
Introduction
.
1.1. The matrix completion problem. This paper is concerned with the completion
problem for positive semidefinite and Euclidean distance matrices. The positive
semidefinite matrix completion problem (P) is defined as follows:
Given a graph E), a subset S ' V and a rational vector a 2 Q S[E , determine
whether there exists a real matrix
(The notation X - 0 means that X is a symmetric positive semidefinite matrix or, for
short, a psd matrix.) In words, problem (P) asks whether a partially specified matrix
can be completed to a psd matrix; the terminology of graphs being used as a convenient
tool for encoding the positions of the specified entries. When problem (P) has a positive
answer, one says that a is completable to a psd matrix; a matrix X satisfying (1.1) is called
a psd completion of a and a positive definite (pd) completion when X is positive definite.
We let (P s ) denote problem (P) when diagonal entries are specified.
If one looks for a pd completion then one can assume without loss of generality that all
diagonal entries are specified (cf. Lemma 2.5); this is however not obviously so if one looks
for a psd completion (although this can be shown to be true when restricting the problem
to the class of chordal graphs; cf. the proof of Theorem 3.5).
i;j=1 is called a Euclidean distance matrix (a distance matrix, for
short) if there exist vectors
CWI, P.O. Box 94079, 1090 GB Amsterdam, The Netherlands (monique@cwi.nl).
M. LAURENT
(Here, kuk denotes the Euclidean norm of vector u 2 R k .) A set of vectors u i satisfying
(1.2) is called a realization of Y . Note that all diagonal entries of a distance matrix are
equal to zero. The Euclidean distance matrix completion problem (D) is defined as follows:
Given a graph E) and a rational vector d 2 determine whether there
exists a real matrix
Y is a distance matrix and y
Hence problem (D) asks whether a partially specified matrix can be completed to a distance
matrix.
As will be recalled in Section 2.3, psd matrices and distance matrices are closely related
and, thus, their associated completion problems can often be treated in an analogous
manner. These matrix completion problems have many applications, e.g., to multidimensional
scaling problems in statistics (cf. [28]), to the molecule conformation problem in
chemistry (cf. [10], [17]), to moment problems in analysis (cf. [5]).
1.2. An excursion to semidefinite programming. The psd matrix completion
problem is obviously an instance of the general semidefinite
programming feasibility problem
Given integral n \Theta n symmetric matrices Q determine whether there
exist real numbers z
The complexity status of problem (F) is a fundamental open question in the theory
of semidefinite programming; this is true for both the Turing machine model and the real
number model, the two most popular models of computation used in complexity theory.
In particular, it is not known whether there exists an algorithm solving (F) whose running
time is polynomial in the size L of the data, that is, the total space needed to store the
entries of the matrices Q
The Turing machine model (also called rational number model, or bit model; cf. [12])
works on rational numbers and, more precisely, on their binary representations; in par-
ticular, the running time of an elementary operation (+; \Gamma; \Theta; \Xi) depends on the length
of the binary representations of the rational numbers involved. Hence, the size L of the
data of problem (F) in this model can be defined as mn 2 L 0 , where L 0 is the maximum
number of bits needed to encode an entry of a matrix Q i . On the other hand, the real
number model (introduced in [9]) works with real numbers and it assumes that exact real
arithmetic can be performed; in particular, an elementary operation (+; \Gamma; \Theta; \Xi) between
any two real numbers takes unit time. Hence, the size L of the data of (F) in this model
is equal to mn 2 .
Semidefinite programming (SDP) deals with the decision problem (F) and its optimization
version:
s.t.
. SDP can be seen as a generalization of linear programming (LP), obtained
by replacing the nonnegativity constraints of the vector variable in LP by the semidefinite-
ness of the matrix variable in SDP. Information about SDP can be found in the handbook
[40]; cf. also the survey [38], and [3, 16] with an emphasis on applications to discrete
optimization.
A standard result in LP is that every feasible linear system: Ax - b with rational
coefficients has a solution whose size is polynomially bounded in terms of the size of A
and b (cf. [36], corollary 3.2b). This implies that the problem of testing feasibility of
an LP program belongs to NP in the bit model (this fact is obvious for the real number
model). Moreover, any LP optimization problem can be solved in polynomial time in the
bit model using the ellipsoid algorithm of Khachiyan [22] or the interior-point method of
Karmarkar [21]; it is an open question whether LP can be solved in polynomial time in
the real number model (cf. p. 60 in [41]).
The feasibility problem (F) belongs to NP in the real number model (since one can
test in polynomial time whether a matrix is psd, for instance, using Gaussian elimination;
in fact, for a rational matrix the running time is polynomial in its bitlength (cf. p. 295
in [15])). However, it is not known whether problem (F) belongs to NP in the bit model.
Indeed, in contrast with LP, it is not true that if a solution exists then one exists which
is rational and has a polynomially bounded size. Consider, for instance, the following
2 is the unique real for which X - 0; hence, this is an instance where there
is a real solution but no rational solution. Consider now the following matrix (taken from
and
thus any rational solution has exponential bitlength. More examples of 'ill-conditioned'
sdp's can be found in [33].
However, Ramana [33] has developed an exact duality theory for SDP which enables
him to show the following results: Problem (F) belongs to NP " co-NP in the real number
model. In the bit model, (F) belongs to NP if and only if it belongs to co-NP; hence,
is not NP-complete nor co-NP complete unless NP=co-NP.
Algorithms have been found that permit to solve the optimization problem (1.5) approximatively
in polynomial time; they are based on the ellipsoid method (cf. [15]) and
interior-point methods (cf. [31], [3]).
4 M. LAURENT
More precisely, set K := fz
S(K; ffl) := fy j 9z 2 K with points that are in the ffl-neighborhood
of K') and S(K; \Gammaffl) ('the points that are at distance at least ffl
from the border of K'). let L denote the maximum bit size of the entries of the matrices
. Assume that we know a constant R ? 0 such that either
with kzk - R. Then, the ellipsoid based algorithm, given rational ffl ? 0, either finds
or asserts that S(K;
Its running time is polynomial in n; m;L and log ffl and this algorithm is polynomial in the
bit model.
Assume that we know a constant R ? 0 such that kzk - R for all z 2 K and a point
z   2 K for which
'strictly feasible'). There is an interior-point
algorithm which finds y 2 K strictly feasible such that c T y -
time polynomial in n; m; L; log ffl; log R and the bitlength of z   . Note, however, that no
polynomial bound has been established for the bitlengths of the intermediate numbers
occurring in the algorithm.
Khachiyan and Porkolab have shown that problem (F) and its analogue in rational
numbers can be solved in polynomial time in the bit model for a fixed number m of
variables.
Theorem 1.1.
(i) [32] Problem (F) can be solved in polynomial time for any fixed m.
(ii) [23] The following problem can be solved in polynomial time for any fixed m:
Given n \Theta n integral symmetric matrices Q rational numbers
satisfying (1.4) or determine that no such numbers exist.
The result from Theorem 1.1 (ii) extends to the context of semidefinite programming the
result of Lenstra [29] on the polynomial solvability of integer LP in fixed dimension.
1.3. Back to the matrix completion problem. As the matrix completion problem
is a special instance of SDP, it can be solved approximatively in polynomial time;
specific interior-point algorithms for finding approximate psd and distance matrix completions
have been developed, e.g., in [19],[10],[2],[30]. However, such algorithms are not
garanteed to find exact completions in polynomial time. This motivates our study in
this paper of some classes of matrix completion problems that can be solved exactly in
polynomial time.
As mentioned earlier, one of the difficulties in the complexity analysis of SDP arises
from the fact that a rational SDP problem might have no rational solution (recall the
example from (1.6)). This raises the following question in the context of matrix completion:
If a rational partial matrix has a psd completion, does a rational completion always
exist ?
We do not know of a counterexample to this statement. On the other hand, we will show
that the answer is positive, e.g., when the graph of specified entries is chordal or has
minimum fill-in 1 (cf. Lemma 4.2). (Note that the answer is obviously positive if a pd
completion exists.)
Motivated by the above discussion, let us define for each of the problems (P) and (D)
its rational analogue (P Q ) and (D Q ). Problem (P Q ) is defined as follows:
Given a graph E), a subset S ' V and a rational vector a 2 Q S[E , find a
rational matrix X satisfying (1.1) or determine that no such matrix exists.
diagonal entries are specified), we denote the problem as (P Q
Problem (D Q ) is defined as follows:
Given a graph E) and a rational vector d 2 rational matrix Y
satisfying (1.3) or determine that no such matrix exists.
The complexity of the problems (P), (D), (P Q ), and (D Q ) is not known; in particular,
it is not known whether they belong to NP in the bit model (they do trivially in the
real number model). In this paper, we present some instances of graphs for which the
completion problems can be solved in polynomial time. All our complexity results apply
for the bit model (unless otherwise specified, as in Section 5.3).
Recall that a graph is said to be chordal if it does not contain a circuit of length - 4
as an induced subgraph. Then, the minimum fill-in of graph G is defined as the minimum
number of edges needed to be added to G in order to obtain a chordal graph. Note that
computing the minimum fill-in of a graph is an NP-hard problem [42]. The following is
the main result of Sections 3 and 4.
Theorem 1.2. For any integer m - 0, problems (P), (P Q ), (D) and (D Q ) can be
solved in polynomial time (in the bit model) when restricted to the class of graphs whose
minimum fill-in is equal to m.
The essential ingredients in the proof of Theorem 1.2 are the subcase
case), Theorem 1.1, and the link (exposed in Section 2.3) between psd matrices and distance
matrices. In the chordal case, a simple combinatorial algorithm permits to solve the
completion problem in polynomial time.
The psd matrix completion problem for chordal graphs has been extensively studied
in the literature (cf. the survey of Johnson [18] for detailed references). In some sense,
this problem has been solved by Grone, Johnson, S'a and Wolkowicz [14] who, building
upon a result of Dym and Gohberg [11], have characterized when a vector a indexed by
the nodes and edges of a chordal graph admits a psd completion; cf. Theorem 3.1. From
this follows the polynomial time solvability of problem (P s ) for chordal graphs. In fact,
the result from Theorem 3.1 is proved in [14] in a constructive manner and, thus, yields
an algorithm permitting to solve problem (P Q
s ) for chordal graphs. This algorithm has
a polynomial running time in the real number model; however, it has to be modified in
order to achieve a polynomial running time in the bit model.
To summarize, the result from Theorem 1.2 also holds in the real number model for
chordal graphs would hold for all graphs having fixed minimum fill-in m - 1
if the result from Theorem 1.1 would remain valid in the real number model 1 .
We present in Section 5.1 another class of graphs for which the matrix completion
problem (P s ) can be solved in polynomial time (in the bit model). This class contains
(generalized) circuits and wheels having a fixed length (and fatness); these graphs arise
naturally when considering the polar approach to the psd matrix completion problem.
Then, Section 5.2 contains a brief description of this polar approach, together with some
open questions and remarks. In the final Section 5.3, we consider the matrix completion
problem for the class of graphs containing no homeomorph of K 4 (it contains circuits).
Then a condition characterizing existence of a psd or distance matrix completion exists
which permits to obtain a simple combinatorial algorithm solving the existence and construction
problems in polynomial time in the real number model.
claims to have a proof of this fact.
6 M. LAURENT
2. Preliminaries. We recall here some basic facts about Schur complements and Euclidean
distance matrices that will be needed in the paper and we make a few observations
about psd completions.
2.1. Schur complements. For a symmetric matrix M , set In(M) := (p; q; r), where
denotes the number of positive (resp. negative, zero) eigenvalues of M .
When M - 0, a maximal nonsingular principal submatrix of M is a nonsingular principal
submatrix of M of largest possible order, thus equal to the rank of M .
Lemma 2.1. Let
be a symmetric matrix, where A is nonsingular.
Then,
the matrix known as the Schur complement of A in M . In particular,
A is a
maximal nonsingular principal submatrix of M , then
As a direct application, we have the following results which will be used at several
occasions in the paper.
Lemma 2.2. Let X be a symmetric matrix having the following block decomposition:
where T , R, Z, A, S, D are rational matrices of suitable orders; all entries of X being
specified except those of Z that have to be determined in order to obtain X - 0. Assume
that
R A
0:
In the case when n - 1 and A 6= 0, let A 0 be a maximal nonsingular principal submatrix
of A, let
denote the corresponding block decompositions of A and X. Then, X - 0 if we set
Z
when
Proof. The result follows using Lemma 2.1 after noting that the Schur complement of
A 0 in X is given by@ T R T
Indeed, the Schur complement
in A is equal to 0 since A - 0 and
A 0 is a maximal nonsingular principal submatrix of A; as implies that
Lemma 2.3. Let X be a symmetric matrix of the form
R A
where A - 0 and T is a symmetric matrix of order ' whose diagonal entries are all equal
to some scalar N . Let A 0 be a maximal nonsingular principal submatrix of A and let
denote the corresponding block decompositions of A and X. Then, X - 0 if and only if (i)
In particular, X is pd if and only if A and
are pd. Moreover, T
large enough (namely, for N
greater or equal to the largest eigenvalue of R T
diagonal
entries and as off-diagonal entries those of T ).
2.2. Some observations about positive semidefinite completions. Given a
graph E), a subset S ' V , a vector a 2 Q S[E , and a scalar N ? 0, let a
denote the extension of a obtained by setting a i := N for all Obviously,
Lemma 2.4. a is completable to a psd matrix if and only if a N is completable to a
psd matrix for some N ? 0 (and then for all N 0 - N ).
Therefore, if one can "guess" a value N to assign to the unspecified diagonal entries, then
one can reduce the problem to the case when all diagonal entries are specified. This can
be done when the graph G of specified off-diagonal entries is chordal as we see later or if
we look for a pd completion as the next result shows.
Lemma 2.5. Given a 2 Q its
restriction to the subgraph induced by S. Then, a has a pd completion if and only if b has
a pd completion.
Proof. Apply Lemma 2.3.
This result does not extend to psd completions (which contradicts a claim from [14] (psd
case in Prop. 1)). Indeed, the following partial matrix@
has no psd completion while its lower principal 2 \Theta 2 submatrix is psd.
8 M. LAURENT
A final observation is that if a partial matrix contains a fully specified row, then the
completion problem can be reduced to considering a matrix of smaller order. Indeed,
suppose that is a partial symmetric matrix whose first row is fully specified. If
a A is not completable. If a then A is completable if and only if its
first row is identically zero and its lower principal submatrix of order
If a 11 ? 0 then one can reduce to a problem of order considering the Schur
complement of a 11 in A.
2.3. Euclidean distance matrices. The following connection (2.4) between psd
and distance matrices has been established by Schoenberg [35]. Let
square symmetric matrix with zeros on its main diagonal and whose rows and columns are
indexed by a set V , and let i 0 be a given element of V . Then, ' i 0 (Y ) denotes the square
whose rows and columns are indexed by set V nfi 0 g
and whose entries are given by
Then, one can easily verify that
Y is a distance matrix
(Indeed, a set of vectors u realization of the matrix Y if and only if ' i 0 (Y )
is the Gram matrix of the vectors u which means that its (i; j)-th
entry is equal to establishes a linear bijection between the
set of distance matrices of order jV j and the set of psd matrices of order
(2.4) has a direct consequence for the corresponding matrix completion problems. Let
E) be a graph and assume that i 0 2 V is a universal node, i.e., that i 0 is adjacent
to all other nodes of G. Then, an algorithm permitting to solve the psd matrix completion
problem for graph Gni 0 can be used for solving the distance matrix completion problem
for graph G and vice versa. Indeed,
Y is a distance matrix completion of d 2 R E
completion of ' i 0 (d)
(For the definition of ' i 0 (d) use (2.3) restricted to the pairs ij with
or i 6= j with ij edge of G.) For more information about connections between the two
problems, see [20],[26].
3. The Matrix Completion Problem for Chordal Graphs. We consider here
the matrix completion problems for chordal graphs. First, we recall results from [14] and
[4] yielding a good characterization for the existence of a completion; then, we see how
they can be used for constructing a completion in polynomial time.
3.1. Characterizing existence of a completion. Let E) be a graph and
let a 2 Q V [E be a vector; in the distance matrix case, the entries of a indexed by V
(corresponding to the diagonal entries of a matrix completion) are assumed to be equal to
zero. If K ' V is a clique in G (i.e., any two distinct nodes in K are joined by an edge
in G), the entries a ij of vector a are well-defined for all nodes
denote the jKj \Theta jKj symmetric matrix whose rows and columns are indexed by K and
with ij-th entry a ij for Obviously, if a is completable to a psd matrix, then a
satisfies:
for every maximal clique K in G:
Similarly, if a is a completable to a distance matrix, then a satisfies:
a(K) is a distance matrix for every maximal clique K in G:
The conditions (3.1) and (3.2) are not sufficient in general for ensuring the existence of
a completion. For instance, if E) is a circuit and a 2 Q V [E has all its entries
equal to 1 except one entry on an edge equal to \Gamma1, then a satisfies (3.1) but a is not
completable to a psd matrix. However, if G is a chordal graph, then (3.1) and (3.2) suffice
for ensuring the existence of a completion.
Theorem 3.1. Let E) be a chordal graph and let a 2 R V [E . If a satisfies
(3.1), then a is completable to a psd matrix [14]; if a satisfies (3.2), then a is completable to
a distance matrix [4]; moreover, if a is rational valued, then a admits a rational completion.
As the maximal cliques in a chordal graph can be enumerated in polynomial time
[37] (cf. below) and as one can check positive semidefiniteness of a rational matrix in
polynomial time (cf. [15], p. 295), one can verify whether (3.1) holds in polynomial time
when G is chordal; in view of (2.4), one can also verify whether (3.2) holds in polynomial
time when G is chordal. This implies:
Theorem 3.2. Problems (P s ) and (D) can be solved in polynomial time for chordal
graphs.
The proof given in [14, 4] for Theorem 3.1 is constructive; thus, it provides an algorithm
for constructing a completion and, as we see below, a variant of it can be shown to have a
polynomial running time. The proof is based on the following properties of chordal graphs.
E) be a graph.
Then, G is chordal if and only if it has a perfect elimination ordering; moreover,
such an ordering can be found in polynomial time [34]. An ordering v of the
nodes of a graph E) being called a perfect elimination ordering if, for every
1, the set of nodes v k with k ? j that are adjacent to v j induces a clique
in G. For the clique consisting of node v j together with
the nodes are adjacent to v j ; then the cliques K
maximal cliques of a chordal graph G.
Hence, if G is chordal and not a clique, then one can find (in polynomial time) an edge
which the graph H := G (obtained by adding e to G) is chordal. (Indeed,
let i be the largest index in [1; n] for which there exists j ? i such that v i and v j are
not adjacent in G; then we can choose for e the pair ij as v remains a perfect
elimination ordering for H.)
Moreover, if G is chordal then, for any e 62 E, there exists a unique maximal clique in
containing edge e [14] (easy to check).
Therefore, if G is complete and not a clique, we can order the missing edges in G as
in such a way that the graph G q := chordal for every
q be the unique maximal clique in G q containing edge
e q . Given a 2 Q V [E satisfying (3.1), set G 0 := G and x 0 := a. We execute the following
step for
Find z q 2 Q for which the vector x q :=
This can be done in view of Lemma 2.2 (case applied to the matrix X :=
x q (K q ) and one can choose for z q the rational value given by (2.2). Then, the final vector
M. LAURENT
rational psd completion of a. This shows Theorem 3.1 in
the psd case (the Euclidean distance matrix case being similar).
As mentioned earlier, the preprocessing step (find the suitable ordering e
the missing edges and the cliques K q ) can be done in polynomial time. Then, one can
construct the values z yielding a psd completion of a in p - n 2 steps. Therefore,
the algorithm is polynomial in the real number model. In order to show polynomiality in
the bit model, one has to verify that the encoding sizes of z polynomially
bounded in terms of n and the encoding size of a. This is, however, not clear. Indeed,
both R 0 and S 0 in the definition of z q via (2.2) may involve some previously defined z h for
(in fact, the same may hold for A 0 ); then, we have a quadratic dependence between
z q and the previously defined z which may cause a problem when trying to
prove that the encoding size of z q remains polynomially bounded. However, as we see
below, the above algorithm can be modified to obtain a polynomial running time. The
basic idea is that, instead of adding the missing edges one at a time, one adds them by
'packets' consisting of edges sharing a common endnode. Then, in view of Lemma 2.2,
one can specify simultaneously all the entries on these edges, which permits to achieve a
linear dependency among the z q 's.
3.2. Constructing a psd completion in polynomial time. Let E) be
a chordal graph and let perfect elimination ordering of its nodes. For
and let denote the elements
set F ' := fi ' denote the graph with node set V and edge set
Hence, we have a sequence of graphs:
where each G ' is chordal remains a perfect elimination ordering of its nodes)
and GL is the complete graph. We now show that G ' has only one maximal clique which
is not a clique in G '\Gamma1 .
Lemma 3.3. For there is a unique maximal clique K ' in G ' which is
not a clique in G '\Gamma1 . Moreover, J(i is a clique in G
and the set K ' n J(i ' ) is a clique in G.
Proof. Let K be a maximal clique in G ' which is not a clique in G
first show that J(i ' ) ' K. For this, assume that
By maximality of K, there exists an element i 2 K such that i and j 0
are not adjacent in G ' . Then, since the set [i ' ; n] is a clique in G ' . Therefore, the
pairs ij and ii ' are edges of G ' and, thus, of G. Since the ordering of the nodes is a perfect
elimination ordering for G, this implies that i ' and j must be adjacent in G, yielding a
contradiction.
Suppose now that K;K 0 are two distinct maximal cliques in G ' such that
and exist nodes i 2 K n K 0 that are not adjacent
in G ' . Given a node j 2 J(i ' ), one can easily verify that (i; i is an induced circuit
in G '\Gamma1 , which contradicts the fact that G '\Gamma1 is chordal and, thus, shows unicity of the
clique K ' . It is obvious that K ' n fi ' g is a clique in G '\Gamma1 . We now verify that K ' n J(i ' ) is
a clique in G. For this, note first that i ' is adjacent to every node of K '
G ' and, thus, in G. Suppose now that x 6= y are two nodes in K ' n (J(i that are
not adjacent in G. Then, as xy is an edge of G '\Gamma1 , we have:
y. As i ' is adjacent to both x and y in G this implies that x
and y must be adjacent in G, yielding a contradiction.
We now describe the modified algorithm. Let E) be a chordal graph and let
a Setting x 0 := a, we execute the following step for
Find z ' 2 Q F ' for which the vector x ' :=
Then, the final vector rational psd completion of a. For
instance, we can choose for z ' the value given by relation (2.2), applying Lemma 2.2 to
the matrix X := x ' (K ' ). (Indeed, in view of Lemma 3.3,
can be verified by induction.)
We verify that the encoding sizes of z are polynomially bounded in terms
of n and the encoding size of a. For this, we note that z are determined by a
recurrence of the form:
are matrices of (appropriate) orders - n. A crucial observation is that
all entries of R ' and A ' belong to the set, denoted as A, of entries of a (as K ' n J(i ' ) is
a clique in G, by Lemma 3.3), while the entries of S ' belong to the set A [ Z
Z denotes the set of entries of (z
For r 2 Q, let hri denote the encoding size of r, i.e., the number of bits needed
to encode r in binary notation and, for a vector
i). One can verify that, for two vectors
a denote the maximum encoding length of the entries of vector a and, for
We derive from (3.6) that
for all ' (setting S 0 := 0). This implies that
As L - n, we obtain that all encoding sizes of z are polynomially bounded in
terms of n and the encoding size of a. (We also use here the fact that the entries of A \Gamma1
are polynomially bounded in the input size; cf. chap. 1.3 in [15].) Thus, we have shown:
Theorem 3.4. Problem (P Q
s ) can be solved in polynomial time for chordal graphs.
We finally indicate how to solve the general problem when some diagonal entries are
unspecified.
Theorem 3.5. Problems (P) and (P Q ) can be solved in polynomial time for chordal
graphs.
Proof. Let E) be a chordal graph, let S ' V and let a 2 Q S[E satisfying:
for each maximal clique K ' S (else, we can conclude that a is not completable).
M. LAURENT
Following Lemma 2.4, we search for a scalar N ? 0 such that a is completable if and only
if its extension a N 2 Q V [E (assigning value N to the unspecified diagonal entries) is
completable or, equivalently, a N (K) - 0 for all maximal cliques K in G. Note that each
matrix a N (K) has the same form as matrix X from Lemma 2.3. Therefore, such N exists
if and only if the linear condition (i) from Lemma 2.3 holds for each clique K and an
explicit value for N can be constructed as indicated in Lemma 2.3. Once N has been
determined, we proceed with completing a N by applying the algorithm presented above.
To conclude note that the algorithm presented in this section outputs a pd completion
if one exists.
3.3. Constructing a distance matrix completion. The distance matrix completion
problem for chordal graphs can be solved in an analogous manner. Namely, let
E) be a chordal graph, let
be the sequence of chordal graphs from (3.4), let K ' be the cliques constructed
in Lemma 3.3, and let a 2 Q Setting a 0 := a, we execute the
following step for
Find z ' 2 Q F ' for which the vector x ' := (a
x ' (K ' ) is a distance matrix.
Then, the final vector provides a distance matrix completion of a.
The above step can be performed as follows. If then we let z ' be defined
by z ' (j) := x is a given element of J(i ' ). Otherwise, let
is a universal node in G[K ' ], the subgraph of G induced by
Therefore, in view of relation (2.5), we can find z ' satisfying (3.7) by applying Lemma
2.2. The polynomial running time of the above algorithm follows from the polynomial
running time of the corresponding algorithm in the psd case. Thus, we have shown:
Theorem 3.6. Problem (D Q ) can be solved in polynomial time for chordal graphs.
4. The Matrix Completion Problem for Graphs with Fixed Minimum Fill-
In. In this section we describe an algorithm permitting to solve problems (P), (P Q
and (D Q ) in polynomial time for the graphs having minimum fill-in m, where m - 1 is a
given integer. This algorithm is based on Theorems 1.1, 3.1, 3.2, 3.4 and 3.6.
E) be a graph with minimum fill-in m, let S ' V and let a 2 Q S[E be
given. (Again we assume that a in the distance matrix case.) We first
execute the following step.
Step 0. Find edges which the graph H :=
chordal and find the maximal cliques K (Such edges exist since G has
and they can be found in polynomial time, simply by enumeration as
m is fixed. The maximal cliques in H can also be enumerated in polynomial time since H
is chordal and, moreover, p - n.)
Then, we perform step x in order to solve problem (x) for x=P,P Q ,D,D Q .
Step P. Determine whether there exist real numbers z for which the vector
defined by x i := a
x eh := z h
Step D. Determine whether there exist real numbers z for which the vector x 2
defined by x
are distance matrices.
Then, a has a completion if and only if the answer in step P or D is positive.
Step P Q . Find rational numbers z holds or determine that
no such numbers exist; if they exist, find a rational psd completion of x.
Step D Q . Find rational numbers z holds or determine that no
such numbers exist; if they exist, find a rational distance matrix completion of x.
Steps P and P Q can be executed in the following manner. Let M denote the block
diagonal matrix with the p matrices x(K 1 diagonal blocks (and zeros else-
Hence, M has order jK holds if and only if M - 0.
Clearly, the matrix M can be written under the form:
are symmetric matrices with (0,1)-entries and Q 0 is a symmetric
matrix whose nonzero entries belong to the set of entries of a. Therefore, in view of
Theorem 1.1, one can determine the existence of z satisfying (4.1) in polynomial
time. Then, finding a rational psd completion of x in step P Q can be done in polynomial
time in view of Theorem 3.4.
In the distance matrix case, we use the following construction for distance matrices.
For a be a square symmetric matrix whose rows and columns are indexed
by set V a and let i a be a given element of V a . We construct a new matrix D, denoted as
whose rows and columns are indexed by set and whose entries
are given by
ae D a (i;
D a (i; i a
Lemma 4.1. D is a distance matrix if and only if D are distance
matrices.
Proof. The 'only if' part is obvious. Conversely, assume that D are distance
matrices; we show that D := D 1 is a distance matrix. For a 2 [1; p], let u a
a ) be vectors providing a realization of D a ; we can assume without loss of generality
that u a
i a
we construct a sequence of vectors w i 2 R n1+:::+np (i 2
setting w i := (0
denotes the zero vector in
R n ). One can easily verify that the vectors w i provide a realization of D.
Steps D and D Q can be performed as follows. Let M := x(K 1
the matrix indexed by K constructed as indicated in relation (4.3). Clearly,
M can be written under the form:
14 M. LAURENT
are symmetric matrices with entries in f0; 1g and Q 0 is a symmetric
matrix whose nonzero entries are sums of at most two entries of a. Let i 0 be a given
element of K
Hence, (4.2) holds if and only if matrix M is a distance matrix (by Lemma 4.1) or,
equivalently, if and only if ' i 0 (M) is positive semidefinite (by relation (2.4)). Therefore,
in view of Theorems 3.2 and 3.6, steps D and D Q can be executed in polynomial time.
This completes the proof of Theorem 1.2.
Lemma 4.2. When the minimum fill-in m is equal to 1, existence of a completion
implies existence of a rational one.
Proof. To see it, suppose first that all diagonal entries are specified; then, steps P and
P Q can be executed in an elementary manner. Indeed, each matrix x(K i
has at most one unspecified entry z 1 . Hence, the set of scalars z 1 for which x(K i
an interval of the form I
to see from Lemma
2.2). Therefore, (4.1) holds if and only if z 1 2
I
and v := min i there is a completion (i.e., if u - v), then one can
find one with z 1 rational. This is obvious if this follows from the fact
(easy to verify) that
Suppose now some diagonal entries are unspecified. If there is a completion with value z 2
at the unspecified diagonal entries, then we can assume that z 2 is rational (replacing if
necessary z 2 by a larger rational number). Then, by the above discussion, the off-diagonal
unspecified entry z 1 can also be chosen to be rational.
5. Further Results and Open Questions. We present in Section 5.1 another class
of graphs for which the completion problem can be solved in polynomial time (in the bit
model). Then, we discuss in Section 5.2 some open questions arising when considering a
polar approach to the positive semidefinite completion problem. Finally, we describe in
Section 5.3 a simple combinatorial algorithm permitting to solve the completion problem
in polynomial time (in the real number model) for the class of graphs containing no
homeomorph of K 4 .
5.1. Another class of polynomial instances. We present here another class of
graphs for which the positive semidefinite matrix completion problem (P s ) can be solved
in polynomial time. Given two integers p;q be the class consisting of the
E) satisfying the following properties: There exist two disjoint subsets
is disjoint from
E, the graph
is chordal, and H has q maximal cliques that are not cliques in G. We show:
Theorem 5.1. Given integers p; q - 1, the positive semidefinite completion problem
can be solved in polynomial time (in the bit model) over the class G p;q .
Examples of graphs belonging to class G p;q arise from circuits, wheels and some gen-
eralizations. A generalized circuit of length n is defined in the following manner: its node
set is U with two nodes being adjacent if and only if
generalized wheel of length n is obtained by adding a set U 0 (the
center of the wheel) of pairwise adjacent nodes to a generalized circuit of length n and
making each node in U 0 adjacent to each node in U Call a generalized circuit
or wheel p-fat if min(jU p-fat generalized circuit or wheel
of length q belongs to G p;q . We will see in Section 5.2 that generalized circuits and
wheels arise as basic objects when studying the matrix completion problem on graphs of
small order.
figwheel.eps
Fig. 5.1. (a) The wheel of length 4; (b) a 2-fat generalized wheel of length 4
The proof of Theorem 5.1 is based on the following result of Barvinok [8], which shows
that one can test feasibility of a system of quadratic equations in polynomial time for any
fixed number of equations 2 .
Theorem 5.2. For
be a quadratic polynomial
in x 2 R n , where A i is an n \Theta n symmetric matrix, b i 2 R n and c i 2 R. One
can test feasibility of the system: f i in polynomial time (in the bit
model) for any given m.
Proof of Theorem 5.1. Let E) be a graph in class G p;q and let a 2 R V [E be
given. We are also given the sets V 1 and V 2 for which, say, adding
to G all edges in F := fij creates a chordal graph H . We show that
deciding whether a can be completed to a psd matrix amounts to testing the feasibility of
a system of m quadratic polynomials where m depends only on p and q. As H is chordal,
a is completable to a psd matrix if and only if there exists a matrix Z of order
for which x := (a; Z) 2 R V [E[F satisfies: x(K) - 0 for each maximal clique K in H . We
assume that for each maximal clique K of H contained in G (else, we
can conclude that a is not completable). Consider now a maximal clique K of H which is
not contained in G. Then, x(K) has the following form:
setting the submatrix of Z with row
indices in the notation of Lemma 2.2, we
obtain that x(K) - 0 if and only if the following matrix
is positive semidefinite (we have assumed that A - 0). We can apply again a Schur
decomposition to matrix MK in order to reformulate the condition on Z. Setting TK :=
In [8] Barvinok considers the homogeneous case, where each equation is of the form: f i
for some symmetric matrix A i . However, the general nonhomogeneous case can be derived from it
(Barvinok, personal communication, 1998).
M. LAURENT
we have that
. Let D 0
0 be a largest nonsingular submatrix of D 0 and let
denote the corresponding block decompositions of D 0 and MK . Taking the Schur complement
of D 0
0 in MK , we obtain that MK - 0 if and only if
Let YK := Z[V denote the column submatrix of Z with column indices in
and set
Then,
Therefore, the condition: x(K) - 0 can be rewritten as the sytem:
ae
are matrices depending on input data a. We can reformulate condition
(1K) as an equation by introducing a new square matrix SK of order
namely, rewrite (1K) as
the columns of matrix Z, and let s K
denote the columns of matrix SK for each clique K. Then, condition (1'K) can be expressed
as a system of
equations of the form:
where f is a quadratic polynomial; similarly for condition (2K). The total number of
quadratic equations obtained in this manner depends only on p and q. Therefore, in view
of Theorem 5.2, one can check feasibility of this system in polynomial time when p and q
are fixed.
p;q denote the subclass of G p;q consisting of the graphs G for which every maximal
clique of H (the chordal extension of G) which is not a clique of G is not contained
in Then, the Euclidean distance matrix completion problem can be solved in
figX.eps
Fig. 5.2. The matrix completion problem for generalized circuits of length 4
polynomial time over the class G 0
p;q for any fixed p and q. The proof is similar to that of
Theorem 5.1, since we can get back to the psd case using relation (2.4) (a matrix and its
image under ' i 0 having same pattern of unknown entries if i 0 belongs to V n In
particular, the Euclidean distance matrix completion problem can be solved in polynomial
time for generalized circuits of length 4 and fixed fatness, or for generalized wheels (with
a nonempty center) of fixed length and fatness.
The complexity of the psd completion problem for generalized wheels and circuits
is not known; in fact, in view of the remark made at the end of Section 2.2, it suffices
to consider circuits. In view of Theorem 5.1, the problem is polynomial if we fix the
length and the fatness of the circuit. It would be particularly interesting to determine the
complexity of the completion problem for generalized circuits of length 4 and unrestricted
fatness. This problem can be reformulated as follows: Determine whether and how one
can fill the unspecified entries in the blocks marked '?' of the matrix X shown in Figure
5.2, so as to obtain X - 0 (all entries are assumed to be specified in the grey blocks).
Indeed, as will be seen in Section 5.2, these graphs constitute in some sense the next case
to consider after chordal graphs.
5.2. A polar approach to the completion problem. Given a graph
consider the cone CG consisting of the matrices
lies on an extremal ray
of the cone CG (i.e.,
define the order of G as the maximum rank of an extremal matrix X 2 CG . It is shown
in [1] that a 2 R V [E is completable to a psd matrix if and only if a satisfies:
a
for every extremal matrix One might suspect that the psd matrix
completion problem is somewhat easier to solve for graphs having a small order since the
extremal matrices in CG have then a small rank. Indeed, the graphs of order 1 are precisely
the chordal graphs, for which the problem is polynomially solvable. On the other hand,
a circuit of length n has order which is the highest possible order for a graph on n
nodes. Moreover, if i 0 is a universal node in a graph G, then both graphs G and G n i 0
have the same order, which corroborates the observation made at the end of Section 2.2.
A natural question concerns the complexity of the problem for graphs of order 2.
The graphs of order 2 have been characterized in [27]. It is shown there that, up to a
simple graph operation (clique-sum), they belong to two basic classes G 1 and G 2 . All the
graphs in G 1 have minimum fill-in at most 3; hence, the problem is polynomially solvable
for them (by Theorem 1.2). The graphs in class G 2 are the generalized wheels of length 4
(and unrestricted fatness). Hence, if the psd matrix completion problem is polynomially
solvable for generalized wheels of length 4, then the same holds for all graphs of order 2.
5.3. The matrix completion problem for graphs with no homeomorph of
K 4 . We now discuss the matrix completion problem for the class H consisting of the graphs
M. LAURENT
figK4.eps
Fig. 5.3. A homeomorph of K 4
containing no homeomorph of K 4 as a subgraph; a homeomorph of K 4 being obtained from
K 4 by repacing its edges by paths. (Graphs in H are also known as series parallel graphs.)
Clearly, H contains all circuits. The case of circuits is certainly interesting to understand
since circuits are the most simple nonchordal graphs.
Similarly to the chordal case, a condition characterizing existence of a psd completion
is known for the graphs in H. Namely, the following is shown in [24] (using a result of [7]).
Given a graph E) in H and a 2 R V [E satisfying: a then a has a
psd completion if and only if the scalars x e := 1
- arccos a e (e 2 E) satisfy the inequalities:
G; jF j odd.
Proposition 5.3. [6] Given x 2 [0; test in polynomial time whether x
satisfies the linear system (5.2).
Proof. Consider the graph ~
E)
consists of
the pairs ij;
is easy to see that x satisfies (5.2) if and only if z(P
for every path P from i to i 0 in ~
G and every . The result now follows as one can
compute shortest paths in polynomial time.
Therefore, problem (P s ) is polynomial time solvable in the real number model for
graphs in H. It is not clear how to extend this result to the bit model since the scalars
- arccos a e are in general irrational and, thus, one encounters problems of numerical
stability when trying to check whether (5.2) holds.
Moreover, there is a simple combinatorial algorithm (already briefly mentioned in [25])
permitting to construct a psd completion in polynomial time in the real number model.
E) be a graph in H and let a 2 R V [E be given satisfying a
The algorithm performs the following steps.
1. Set x e := 1
- arccos a e for e 2 E and test whether x satisfies (5.2). If not, one can
conclude that a has no psd completion. Otherwise, go to 2.
2. Find a set F of edges disjoint from E for which the graph H :=
and contains no homeomorph of K 4 .
3. Find an extension y 2 [0; 1] E[F of x satisfying the linear system (5.2) with respect to
graph H .
4. Set b e := cos(-y e ) for e is completable to a psd
matrix (since y satisfies (5.2) and H has no homeomorph of K 4 ) and one can compute a
psd completion X of b with the algorithm of Section 3.2 (since H is chordal). Then, X is
a completion of a.
All steps can be executed in polynomial time. This follows from earlier results for
steps 1 and 4; for step 2 use a result of [39] and, for step 3, one can use an argument
similar to the proof of Proposition 5.3. Namely, given x 2 [0; satisfying (5.2), in order
to extend x to [0; 1] E[feg in such a way that (5.2) remains valid with respect to G+ e, one
has to find a scalar ff 2 [0;
We have:
;. With the notation of the proof of Proposition 5.3, one finds that
is an ab path in ~
is an ab \Gamma path in ~
Hence one can compute ff in polytime. One can then determine the extension y of x to H
by iteratively applying this procedure.
The distance matrix completion problem for graphs in H can be treated in a similar
manner. Indeed, given E) in H and a 2 R E
a e for e 2 E. Then, a is
completable to a distance matrix if and only if x satisfies the linear inequalities:
f2Cne
circuits C in G and all e 2 C:
(Cf. [26].) Again one can test in polynomial time whether x - 0 satisfies (5.3) (simply,
test for each edge is an ab \Gamma path in G)). An
algorithm analogous to the one exposed in the psd case permits to construct a distance
matrix completion. Therefore, we have shown:
Theorem 5.4. One can construct a real psd (distance matrix) completion or decide
that none exists in polynomial time in the real number model for the graphs containing no
homeomorph of K 4 .
It is an open question whether the above result extends to the bit model of computa-
tion, even for the simplest case of circuits.

Acknowledgements

. We are grateful to A. Barvinok for providing us insight about
Theorem 5.2, to L. Porkolab for bringing [23] to our attention, and to A. Schrijver for
discussions about Section 3. We also thank the referees for their careful reading and for
their suggestions which helped us improving the presentation of the paper.



--R

Positive semidefinite matrices with a given sparsity pattern.
Solving Euclidean distance matrix completion problems via semidefinite programming.
Interior point methods in semidefinite programming with applications in combinatorial optimization.
The Euclidean distance matrix completion problem.
On the matrix completion method for multidimensional moment problems.

The real positive definite completion problem for a simple cycle.
Feasibility testing for systems of real quadratic equations.
On a theory of computation and complexity over the real num- bers: NP-completeness
Distance Geometry and Molecular Conformation.
Extensions of band matrices with band inverses.
Computers and Intractability: A Guide to the Theory of NP- Completeness
Algorithmic Theory and Perfect Graphs.


An interior-point method for semidefinite programming
The molecule problem: exploiting structure in global optimization.
Matrix completion problems: a survey.
An interior-point method for approximate positive semidefinite completions
Connections between the real positive semidefinite and distance matrix completion problems.
A new polynomial-time algorithm for linear programming
A polynomial algorithm in linear programming.
Computing integral points in convex semi-algebraic sets
The real positive semidefinite completion problem for series-parallel graphs
Cuts, matrix completions and graph rigidity.
A connection between positive semidefinite and Euclidean distance matrix completion problems.
On the order of a graph and its deficiency in chordality.
Theory of multidimensional scaling.


Interior Point Polynomial Algorithms in Convex Program- ming: Theory and Algorithms
On the complexity of semidefinite programs.
An exact duality theory for semidefinite programming and its complexity implica- tions
Algorithmic aspects of vertex elimination on graphs.
Remarks to M.
Theory of Linear and Integer Programming.
Decomposition by clique separators.
programming.
Steiner trees
Handbook of Semidefinite Program- ming: Theory

Computing the minimum fill-in is NP-complete
--TR

--CTR
Henry Wolkowicz , Miguel F. Anjos, Semidefinite programming for discrete optimization and matrix completion problems, Discrete Applied Mathematics, v.123 n.1-3, p.513-577, 15 November 2002
real number model;chordal graph;positive semidefinite matrix;polynomial algorithm;euclidean distance matrix;order of a graph;minimum fill-in;bit model;matrix completion