Algorithms for Euclidean Distance Matrix Completion: Exploiting Proximity to Triviality

Let $X$ be a set. A function $\rho :X\times X\to {ℝ}_{\ge 0}$ is a distance on $X$ if: (i) $\rho$ is symmetric, that is, for any $x,y\in X$, $\rho (x,y)=\rho (y,x)$, and (ii) $\rho (x,x)=0$ for all $x\in X$. Then, $(X,\rho )$ is called a distance space. A distance space $(X,\rho )$ for a finite $X=\{x_1,\mathrm{\dots },x_n\}$ can be equivalently defined by the distance matrix, in which the value in row $i$ and column $j$ is ${\rho }_{ij}^2$, where ${\rho }_{ij}=\rho (x_i,x_j)$ for $i,j\in \{1,\mathrm{\dots },n\}$. Throughout the paper we do not distinguish metric spaces and the corresponding distance matrices.

A distance space $(X,\rho )$ is isometrically embeddable into ${ℝ}^d$ if there is a map, called isometric embedding, $\phi :X\to {ℝ}^d$ such that $\rho (x,y)={\Vert \phi (x)-\phi (y)\Vert }_2$ for all $x,y\in X$, where ${\Vert p-q\Vert }_2=\sqrt{⟨p,p⟩+⟨q,q⟩-2⟨p,q⟩}$ for $p,q\in {ℝ}^d$. Notice that we do not require $\phi$ to be injective, that is, several points of $(X,\rho )$ may be mapped to the same point of ${ℝ}^d$. Throughout the paper, whenever we mention an embedding, we mean an isometric embedding. Moreover, when we use the term $d$-embedding, we are referring to embedding into ${ℝ}^d$. A $d$-embeddable distance space is strongly $d$-embeddable if it is not $(d-1)$-embeddable. As convention, we assume that the empty set of points is $d$-embeddable for every $d$. A symmetric $n\times n$ matrix $D=(d_{ij})$ over ${ℝ}_{\ge 0}$ with $d_{ii}=0$ for all $i\in \{1,\mathrm{\dots },n\}$ is a Euclidean distance matrix (EDM) in ${ℝ}^d$ if $D=D(\rho )$ is the distance matrix of a distance space $(X,\rho )$ embeddable in ${ℝ}^d$. Suppose that $𝒳=(X,\rho )$ is embeddable into ${ℝ}^d$. The ordered set $P=(p_1,\mathrm{\dots },p_n)$ of points in ${ℝ}^d$ is said to be a realization of $𝒳$ if there is an embedding $\phi :X\to {ℝ}^d$ such that $\phi (x_i)=p_i$ for all $i\in \{1,\mathrm{\dots },n\}$.

For a $d$-embeddable distance space $(X,\rho )$, a set $Y\subseteq X$ is a metric basis if, given an isometric embedding $\phi$ of $(Y,\rho )$ into ${ℝ}^d$, there is a unique way to extend $\phi$ to an isometric embedding of $(X,\rho )$. Equivalently, if a realization of $(Y,\rho )$ is fixed then the embedding of any point of $X\setminus Y$ in a $d$-embedding of $(X,\rho )$ is unique. In our paper we also use the embeddablity characterization based on the properties of Cayley-Menger matrices. Towards this, we use terminology and notation from [6]. For $r+1$ points $x_0,x_1,\mathrm{\dots },x_r$ of distance space $(X,\rho )$ the Cayley-Menger determinant $CM(x_0,x_1,\mathrm{\dots },x_r)$ is the determinant of the matrix obtained from the distance matrix induced by these points by prepending a row and a column whose first element is zero and the other elements are one.

Let $(X,\rho )$ be a distance space. For a nonnegative integer $r$, we say that $Y\subseteq X$ of size $r+1$ is independent if $(Y,\rho )$ is strongly $r$-embeddable.

We remind that by our convention, we do not distinguish metric spaces and the corresponding distance matrices. Thus, we say that an $n$-tuple of points of ${ℝ}^d$ is a realization of an $n\times n$ distance matrix. Furthermore, we say that a subset of indices $X\subseteq \{1,\mathrm{\dots },n\}$ is a metric basis of the distance matrix meaning that the corresponding points of the distance space compose a metric basis for it. In this spirit, if $M$ is the distance matrix of a (strongly) $d$-embeddable distance space, then we say that $M$ is a (strongly) $d$-embeddable EDM.

We consider simple finite undirected graphs and refer to [20] for the standard graph-theoretic notation. Given a graph $G$, we denote by $V(G)$ and $E(G)$ the sets of vertices and edges, respectively. Throughout the paper we use $n$ and $m$ for $|V(G)|$ and $|E(G)|$, respectively, if the graph is clear from the context. A set of pairwise adjacent vertices $K$ of $G$ is called a clique and a set of pairwise non-adjacent vertices is independent. A family of $k$ cliques $𝒞=\{C_1,\mathrm{\dots },C_k\}$ of a graph $G$ is en edge clique cover of $G$ if for every edge $uv\in E(G)$, there is $i\in \{1,\mathrm{\dots },k\}$ such that $uv$ is covered by $C_i$, that is, $u,v\in C_i$. For a vertex $v\in V(G)$, we use $N_G(v)$ to denote the open neighborhood of $v$, that is, the set of adjacent to $v$ vertices. The degree $d_G(v)=|N_G(v)|$, and the maximum degree of $G$ is $\mathrm{\Delta }(G)=\max \{d_G(v)\mid v\in V(G)\}$. For a graph $G$, its complement $\overline{G}$ is the graph with the same set of vertices as $G$, and two distinct vertices $u,v\in V(G)$ are adjacent to $\overline{G}$ if and only if they are not adjacent in $G$.

Let $A$ be an $n\times n$ matrix. The matrix obtained from $A$ by deleting $n-k$ rows and $n-k^{\prime }$ columns (with $1\le k,k^{\prime }\le n$) is called a $k\times k^{\prime }$ submatrix of $A$. A principal submatrix of $A$ is a square submatrix obtained by deleting the same set of row and column indices; that is, if the $i$-th row of $A$ is deleted, then the $i$-th column is also deleted. Let $G$ be a graph with $V(G)=\{1,\mathrm{\dots },n\}$. An $n\times n$ matrix $A=(a_{ij})$ over ${ℝ}_{\ge 0}$ with some unspecified elements is said to be a $G$-partial matrix if (i) the entry $a_{ij}$ is defined (or specified) if and only if $ij\in E(G)$, (ii) $a_{ij}=a_{ji}$ for all $ij\in E(G)$, and $a_{ii}=0$ for all $i\in \{1,\mathrm{\dots },n\}$. We also say that $G$ is the underlying graph of $A$. Let $A$ be a $G$-partial matrix and let $d$ be a positive integer. A matrix $D$ is said to be a $d$-EDM completion of $A$ if:

1. 1.

   $D$ is $d$-embeddable, and

2. 2.

   $d_{ij}=a_{ij}$ for all $ij\in E(G)$.

See Figure 3 for an example.

It is convenient for us to combine graph-theoretic and matrix notation. Let $A=(a_{ij})$ be symmetric $n\times n$ matrix and let $G$ be a graph with $V(G)=[n]$. For a set $X\subseteq [n]$, we use $G[X]$ to denote the subgraph of $G$ induced by $X$ and we use $A[X]$ to denote the principal submatrix indexed by $X$, that is, the submatrix of $A$ composed by the elements $a_{ij}$ with $i,j\in X$. We also write $G-X$ and $A-X$ to denote the graph obtained by the deletion of the vertices of $X$ and the submatrix obtained by the deletion of the rows and columns indexed by $X$, respectively, that is, $G-X=G[V(G)\setminus X]$ and $A-X=A[V(G)\setminus X]$. For a set $X=\{x\}$, we write $G-x$ and $A-x$ instead of $G-\{x\}$ and $A-\{x\}$, respectively.

We conclude this section with Theorem 1, which shows that for tractability of $d$-EDMC, it is not sufficient to require high density of the specified element in the input matrix (or, equivalently, high density of the underlying graph $G$).

The main step of the proof is to identify an “irrelevant” vertex of $G$ in polynomial time, that is, a vertex whose deletion does not transform a no-instance into a yes-instance. By exhaustively repeating this step of removing an irrelevant vertex we either solve the problem, or construct an equivalent instance on ${(d+1)}^{𝒪(t^2)}$ rows and columns.

Let $M$ be a $G$-partial matrix, where $G$ excludes a $t$-block pattern. If $t=1$, then $M$ is fully specified (i.e., $G$ is complete) and so, we solve the instance $(M,d)$ using Proposition 17. So, we assume that $t>1$. Let $\eta (d,t)=(d+1)t+(t-1){(d+1)}^{t+1}+1,$ and $\rho (d,t)=\left(\genfrac{}{}{0pt}{}{2t+\eta (d,t)-2}{2t-1}\right).$

If , then the desired compression is already achieved and we simply output $(M,d)$. From now on, we assume that $n\ge \rho (d,t)$. Since $\overline{G}$ is $K_{t,t}$-free, it does not contain a clique of size $2t$. By Ramsey’s classic theorem [22] $\overline{G}$ must therefore contain an independent set $X$ of size $\eta (d,t)$. Moreover, such a set $X$ can be computed in polynomial time. By definition, $X$ induces a clique in $G$. Notice that because $M$ is not fully specified, $V(G)\ne X$.

We use Proposition 17 to check in polynomial time whether $M[X]$ is $d$-embeddable. If not, then we report that $(M,d)$ is a no-instance and stop. For every $v\in V(G)\setminus X$, notice that $C_v=\{v\}\cup (N_G(v)\cap X)$ is a clique of $G$. So, for every $v\in V(G)\setminus X$ we also check whether $M[C_v]$ is $d$-embeddable, and report that $(M,d)$ is a no-instance if it is not.

We next iteratively construct disjoint sets $X_1,\mathrm{\dots },X_t\subseteq X$ of size at most $d+1$ as follows. Assuming that $X_0=\mathrm{\varnothing }$, we select $X_i$ to be a metric basis of $M[X\setminus {\bigcup }_{j=0}^{i-1}{X}_j]$ for $i\in \{1,\mathrm{\dots },t\}$ obtained using Proposition 17. As $|X_i|\le d+1$ for $i\in \{1,\mathrm{\dots },t\}$, we have that $|{\bigcup }_{i=1}^t{X}_i|\le (d+1)t$. Moreover, since $X$ is large enough, the sets $X_1,\mathrm{\dots },X_t$ exist.

Consider $Y=\{y\in V(G)\setminus X:X_i\setminus N_G(y)\ne \mathrm{\varnothing }\text{ for all }i\in \{1,\mathrm{\dots },t\}\}$. That is, $Y$ consists of all vertices outside $X$ having a non-neighbor in each $X_i$ in $G$.

For every $y\in Y$, we consider the clique $K_y=N_G(y)\cap X$. Since $K_y\subseteq C_y$ and we have already concluded that $M[C_y]$ is $d$-embeddable, we have that $M[K_y]$ is $d$-embeddable. We compute a metric basis $Z_y$ of $M[K_y]$ using Proposition 17. Because $|Y|\le (t-1){(d+1)}^t$ by Claim 18 and $|Z_y|\le d+1$ for $y\in Y$, we have that $|{\bigcup }_{y\in Y}{Z}_y|\le (t-1){(d+1)}^{t+1}$. Because $|{\bigcup }_{i=1}^t{X}_i|\le (d+1)t$ and $|X|\ge (d+1)t+(t-1){(d+1)}^{t+1}+1$, we have that there is $w\in X\setminus \left(\left({\bigcup }_{i=1}^t{X}_i\right)\cup \left({\bigcup }_{y\in Y}{Z}_y\right)\right)$.

We set $M:=M-w$ and iterate. In at most $n$ rounds, we either solve the problem or obtain an equivalent instance $(M^{\prime },d)$, where $M^{\prime }$ is a $n^{\prime }\times n^{\prime }$ submatrix of $M$ with . For the running time, note that the construction of the independent set $X$ as well as that of $X_1,\mathrm{\dots },X_t$ is done in polynomial time by Proposition 17. Then $Y$ and the sets $Z_y$ for $y\in Y$ can also be constructed in polynomial time by Proposition 17. So, an irrelevant vertex can be found in polynomial time. Because the total number of rounds is at most $n$, the overall running time is polynomial. $◀$

As discussed, by combining Theorem 4 with Theorem 5, we obtain the following corollary.

In the remaining part of the section, we show that for some other classes of dense graphs $G$, we can obtain a better compression for $d$-EDMC than the one obtained by using Theorem 4 as a black box. The proofs of these results still follow the same lines as the proof of Theorem 4. First, we consider the case when $\overline{G}$ has bounded maximum degree. Since a graph of maximum degree at most $\mathrm{\Delta }$ does not contain $K_{\mathrm{\Delta }+1,\mathrm{\Delta }+1}$, in the following theorem, we consider a subclass of matrices considered in Theorem 4.

Finally in this section, we prove Theorem 11. Notice that Theorem 11 assumes that an edge clique cover is given. However, an edge clique cover of size at most $k$ can be found in $\mathrm{FPT}$ in $k$ time (if exists) by the results of Gramm et al. [30].

Then we obtain the following corollary.

Let the instance $(M,d)$ be given, where $M$ is $G$-partial and moreover, let $X$ be a set of at most $k$ non-edges of $G$ such that $G^{\prime }=G+X$ is a chordal graph. It is straightforward to construct $G$ from $M$ and once we have $G$, we compute $X$ (if it exists) in time $2^{o(k)}{n}^{𝒪(1)}$ using the algorithm of Fomin and Villanger [26]. In the rest of the proof, we will only refer to the graph $G^{\prime }$, so we can refer to the pairs in $X$ as edges. Let $𝒵$ denote a set of $2k$ indeterminates, two per edge in $X$. Formally, for every edge $uv\in X$, $𝒵$ contains the indeterminates $z_{uv}$ and $z_{vu}$. Let $C_1,\mathrm{\dots },C_t$ be the maximal cliques in $G^{\prime }$. It is well-known that $t\le n$ and these cliques can be computed in polynomial time [27].

1. 1.

   Do the following for each $i\in [t]$:

   1. (a)

      Define ${𝒵}_i=\{z_{uv}\mid u,v\in V(C_i)\}$. That is, ${𝒵}_i$ comprises those indeterminates corresponding to those edges in $X$ that have both endpoints in $V(C_i)$.

   2. (b)

      Define $V_X(C_i)=\{u\mid \exists v:uv\in X\wedge \{u,v\}\subseteq V(C_i)\}$. That is, $V_X(C_i)$ is the set of endpoints of edges in $X$ that are contained in $C_i$.

   3. (c)

      Define $B_i$ to be an arbitrary metric basis of $M_i=M[V(C_i)\setminus V_X(C_i)]$. Since by definition, $M_i$ is fully specified, $B_i$ is well-defined. If $|B_i|>d+1$, then stop and conclude that the input is a no-instance.

   4. (d)

      For every $Y\subseteq V_X(C_i)$ of size at most $d+1-|B_i|$, do the following:

      1. i.

         Define $B_i^Y=B_i\cup Y=\{x_0,\mathrm{\dots },x_r\}$.

      2. ii.

         Use Lemma 27 to construct the following set $P_i^Y$ of atoms:

         1. A.

            ${(-1)}^{j+1}C{M}_{Z_i}(x_0,x_1,\mathrm{\dots },x_j)>0$, where $1\le j\le r$.

         2. B.

            $C{M}_{Z_i}(x_0,x_1,\mathrm{\dots },x_r,x)=0$ for every $x\in V(C_i)\setminus B_i^Y$.

         3. C.

            $C{M}_{Z_i}(x_0,x_1,\mathrm{\dots },x_r,x,y)=0$ for every $x,y\in V(C_i)\setminus B_i^Y$.

         4. D.

            $z_{uv}\ge 0$ for each indeterminate $z_{uv}\in Z_i$.

         5. E.

            $z_{uv}-z_{vu}=0$ for each pair $z_{uv},z_{vu}$ of indeterminates in $Z_i$.

      3. iii.

         Define ${\varphi }_i^Y$ to be the quantifier-free formula defined as the conjunction of the atoms in $P_i^Y$.

   5. (e)

      Define ${\mathrm{\Psi }}_i$ to be the quantifier-free formula defined as the disjunction of the formulas ${\varphi }_i^Y$ taken over all $Y\subseteq V_X(C_i)$ of size at most $d+1-|B_i|$.

2. 2.

   Define the quantifier-free formula $\mathrm{\Gamma }={\bigwedge }_{i\in [t]}{\mathrm{\Psi }}_i$.

3. 3.

   Run the algorithm of Proposition 23 on the sentence obtained by existentially quantifying the indeterminates in $𝒵$ and prepending them to $\mathrm{\Gamma }$. Return the same answer as that produced by this invocation.

These three claims complete the proof of the theorem. $◀$