Isometric-Universal Graphs for Trees

Let $𝒰$ be any minimum and minimal isometric-universal graph for $ℱ=\{T_1,T_2\}$ composed of two trees. We consider a given isometric embedding of $T_1$ and $T_2$ in $𝒰$, and denote by $A_1$ and $A_2$ their corresponding embedded subgraphs in $𝒰$. Since $𝒰$ is minimal, $𝒰=A_1\cup A_2$. So, each vertex or edge of $𝒰$, belongs either to $A_1\setminus A_2$, $A_2\setminus A_1$, or to $A_1\cap A_2$.

For convenience, let us denote by $d(x,y)={\mathrm{dist}}_{𝒰}(x,y)$, and by $|P|$ the length of path $P$, i.e., its number of edges. We will often use the property that every path of $P$ of $A_i$, for some $i\in \{1,2\}$, satisfies $|P|={\mathrm{dist}}_{A_i}(u,v)=d(u,v)$, where $u,v$ are the extremities of $P$. This is because every path of a tree is a shortest path in this tree, and because $A_i$ is an isometric subgraph of $𝒰$.

$𝒰$ must be connected, otherwise we could merge two connected components of $𝒰$ by a vertex, and this without modifying any distance in $A_1$ or $A_2$ which are finite. This would contradicting the fact that $𝒰$ is minimum. If $𝒰$ is a tree, we are done. It remains to show that if $𝒰$ has a cycle, then $𝒰$ is not minimum. Consider the shortest cycle $C$ in $𝒰$. Let us show that:

Consider the connected components of $A_1\cap A_2$. Obviously, such components are trees. In particular, $C\subset A_1\cap A_2$ is impossible. It is also clear that $C$ intersects at least two such components. Indeed, first, if it intersects no components, then $C$ is wholly contained in $A_1$ or in $A_2$, contradicting they are trees. Secondly, if it intersects only one, then $C$ is wholly contained in $A_1$ or in $A_2$ as well, since the part of $C$ outside the component exists and belongs to one tree, and the part inside the component belongs to both trees.

Define $u$ and $v$ as any two vertices of $C$ that belong to two different components of $A_1\cap A_2$, and such that ${\mathrm{dist}}_C(u,v)$ is minimum. Let $P_1$ be a path of $C$ realizing this distance. By construction, the only vertices of $P_1$ that are in $A_1\cap A_2$ are precisely its extremities $u,v$. Indeed, if $P_1\setminus \{u,v\}$ contains a vertex $w$ in $A_1\cap A_2$, then both ${\mathrm{dist}}_C(u,w)$ and ${\mathrm{dist}}_C(v,w)$ would be less than ${\mathrm{dist}}_C(u,v)$, which is not possible by the choice of $u,v\in C$. Thus, $P_1\setminus \{u,v\}$ contains only vertices and edges of a same tree $A_i$, because if two consecutive edges belong to different trees, their common vertex must be in the intersection. W.l.o.g., assume that $P_1\subset A_1$. Note that we have ${\mathrm{dist}}_C(u,v)=d_{A_1}(u,v)=d(u,v)=|P_1|$ because $P_1$ is a path of $A_1$. We set $P_2$ to be the path of $C$ induced by the edges of $C$ not in $P_1$.

Clearly, the first two points hold: $P_1\cap P_2=\{u,v\}$ and $u,v\in A_1\cap A_2$, and we have seen that $P_1\setminus \{u,v\}\subset A_1\setminus A_2$, and thus $P_1\setminus P_2\subset A_1\setminus A_2$.

For the third point, by way of contradiction, assume that $P_2\setminus \{u,v\}$ contains a vertex of $w\in A_1\cap A_2$. We have $|P_1|={\mathrm{dist}}_{A_1}(u,v)=d(u,v)$. By the choice of $u$ and $v$ on $C$, we must have $|P_1|+|P_2|⩾2d(u,v)$, i.e., $|P_2|⩾d(u,v)$. On the other hand, let us consider the path $P$ between $u$ and $v$ in $A_2$. We have $|P|={\mathrm{dist}}_{A_2}(u,v)=d(u,v)$. So, $P_1\cup P$ creates a cycle of length at most $2d(u,v)$. By minimality of $C$, this implies that $|P_2|=d(u,v)$. But, if $w\in P_2\setminus \{u,v\}$, then both ${\mathrm{dist}}_C(u,w)$ and ${\mathrm{dist}}_C(v,w)$ would be less than $|P_2|=d(u,v)={\mathrm{dist}}_C(u,v)$: a contradiction with the choice of $u,v\in A_1\cap A_2$ that minimizes the distance on $C$. So, $P_2\setminus P_1$ has no vertex in $A_1\cap A_2$. Thus, $P_2\setminus P_1$ contains only vertices and edges of a same tree $A_i$. Clearly, $P_2\setminus P_1\subset A_1$ is not possible, since otherwise $C$ would be wholly contained in $A_1$. So, $P_2\setminus P_1\subset A_2\setminus A_1$ as required. $\mathrm{⊲}$

Let $u,v,P_1,P_2$ be as in Claim 3. Note that $d(u,v)>1$. Indeed, we have seen that the size of $C$ is $|P_1|+|P_2|=2d(u,v)$, and $d(u,v)=1$ is not possible since $C$ is a cycle. Then, we can define $w_i$ to be the neighbor of $u$ in $P_i$, for each $i\in \{1,2\}$. See Figure 2 on the left. And, consider the graph ${𝒰}^{\prime }$ obtained from $𝒰$ by identifying $w_1$ and $w_2$ into a new vertex $w$, and by removing double edges created. We call this operation on $𝒰$ a contraction, since it corresponds to a classical edge-contraction if $w_1$ and $w_2$ are adjacent. See Figure 2.

We will show that ${𝒰}^{\prime }$ is still isometric-universal for $ℱ$, contradicting the fact that $𝒰$ has the minimum number of vertices. This will prove that $C$ does not exist in $𝒰$, and so $𝒰$ is a tree.

Let us show that $A_1$ and $A_2$ are isometric subgraphs of ${𝒰}^{\prime }$. We have to prove that the contraction of $w_1$ and $w_2$ does not change any distance between any pair of vertices that belong to a same tree $A_i$, for each $i\in \{1,2\}$.

First we remark that $A_i$ is a subgraph of ${𝒰}^{\prime }$. Indeed, $w_1$ and $w_2$ belong to different trees, and thus the edge $u-w_i$ of $A_i$ in $𝒰$, after contraction, is in $A_1\cap A_2$ in ${𝒰}^{\prime }$. So, the distances between vertices taken in $A_i$ can only decrease in ${𝒰}^{\prime }$.

We proceed by way of contradiction. Assume there are two vertices $x$ and $y$ at distance $d$ in $𝒰$ that both belong to $A_i$, for some $i$, and such that . We consider only the case $A_i=A_1$, the case $A_i=A_2$ being symmetric.

Let us show that:

For every path $Q$ in $𝒰$, we denote by $\widehat{Q}$, its contraction, i.e., the path obtained by contracting all the edges of the subpath of $Q$ between $w_1$ and $w_2$. If $w_1$ or $w_2$ is not in $Q$, we set $\widehat{Q}=Q$. Note that $\widehat{Q}$ is a path of ${𝒰}^{\prime }$.

Let $P^{\prime }$ be a shortest path in ${𝒰}^{\prime }$ between $x$ and $y$. By hypothesis on $x,y$, . Let us show that there exists a path $P$ in $𝒰$ such that $P^{\prime }=\widehat{P}$ and $|P|⩽d+1$. If $P^{\prime }$ does not contain $w$, then $P=P^{\prime }=\widehat{P}$. Otherwise, $w\in P^{\prime }$. There are two cases: (1) if $P^{\prime }$ contain $uw$, then we can set $P$ as the path $P^{\prime }$ where $w$ is replaced $w_1$ or $w_2$ (depending on the other edge incident to $w$ in $P^{\prime }$); (2) if $P^{\prime }$ does not contain $uw$, then since $P^{\prime }$ is a shortest path, it cannot contain $u$. We can set $P$ as the path $P^{\prime }$ where $w$ is replaced by the path $w_1-u-w_2$ or $w_2-u-w_1$. We check that in both cases, $\widehat{P}=P^{\prime }$, and , that implies $|P|⩽d+1$. $\mathrm{⊲}$

Let $P$ be a path as in Claim 4. Note that $P$ is a witness for , i.e., a path connecting $x$ to $y$ and such that after contracting $w_1$ and $w_2$, its length decreases by $2$ in ${𝒰}^{\prime }$, and becomes less than $d$. W.l.o.g. we will assume that $P$ visits $w_1-u-w_2$ in this order when going from $x$ to $y$. If not, we can exchange the role of $x$ and $y$.

Now, let us define the vertices $a,b,z$ as follows (see Figure 3):

• $\mathrm{■}$

  Vertex $b$ is the last vertex of $P$, when going from $u$ to $y$, that belongs to $P_2$. Note that $b$ is between $w_2$ and $y$ on $P$, possibly with $b=w_2$. See Figure 3 on the left.

• $\mathrm{■}$

  Vertex $z$ is the first vertex of $P$, when going from $b$ to $y$, that belongs to $A_1$, possibly with $z=y$. Note that $z\ne b$. See Figure 3 on the right.

• $\mathrm{■}$

  Vertex $a$ is the last vertex of the path between $u$ to $z$ in $A_1$, when going from $u$ to $z$, that belongs to $P_1$, possibly with $a\in \{u,w_1,v\}$. See Figure 3 on the right.

Since $P$ passes successively through vertices $x,w_1,u,w_2,b,z,y$, we have:

The quantity $d(w_1,u)+d(u,w_2)$ is equal to $2$, since $w_1,u,w_2$ are consecutive in $P$. On the other hand, $|P|⩽d+1$ by definition of $P$. By the triangle inequality between $x$ and $y$, $d=d(x,y)⩽d(x,w_1)+d(w_1,a)+d(a,z)+d(z,y)$. Therefore:

In fact, we will show that:

Before presenting its proof, observe that the inequality of Claim 5 contradicts Equation 1, and the fact that some distance between two vertices of the same tree, namely $x$ and $y$, is shortened in ${𝒰}^{\prime }$. So ${𝒰}^{\prime }$ is universal-isometric for $\{A_1,A_2\}$, and thus $𝒰$ cannot be minimum, and thus does not contain any cycle.

We will actually prove a stronger statement which is:

We first remark that vertex $z\in A_1\cap A_2$. Indeed, we have $z\in A_1$. If $z\notin A_2$, then the edge $z-z^{\prime }$ on the path $P$ from $z$ to $b$ is not in $A_2$. So, $z-z^{\prime }\in A_1$, which implies $z^{\prime }\in A_1$: a contradiction with the fact that $z$ is the first vertex on $P$ from $b$ to $y$ that is in $P_1$. So $z\in A_1\cap A_2$.

As a preliminary step, let us show that $d(u,a)=d(u,b)$, cf. Equation 5 hereafter. Recall that $u,v,z\in A_1\cap A_2$, and that distances in $A_i$ coincide with distances in $𝒰$.

By definition, $a$ is on the path from $u$ to $z$ in $A_1$. Thus

Similarly for $b$, which is on the path in $A_2$ from $u$ to $z$, we have $d(u,z)=d(u,b)+d(b,z)$. Combining these two equations, we get:

We use the following fact:

In particular, whenever applied to $u,v$ and $z$ in $A_1$, pairwise connected by the three tree paths $P_{uv},P_{vz},P_{uz}$ in $A_1$, the fact implies the last vertex of $P_{uz}$ that is on $P_{uv}$ is also the last vertex of $P_{vz}$ that is on $P_{uv}$. From this, we deduce that $a$ is on the path from $v$ to $z$ in $A_1$. Thus $d(v,z)=d(v,a)+d(a,z)$. With the same argument applied to the same vertices but in $A_2$, we deduce that $b$ is on the shortest path in $A_2$ from $v$ to $z$, we have $d(v,z)=d(v,b)+d(b,z)$. Therefore:

By subtracting Equation 3 from Equation 2, we have:

Note that $P_1$ and $P_2$ are paths of $A_1$ and $A_2$ respectively, thus they are shortest paths in $𝒰$. Since $a$ and $b$ are on $P_1$ and $P_2$ respectively, we have $d(u,v)=d(u,a)+d(a,v)=d(u,b)+d(b,v)$. And by adding to Equation 4, we get:

as claimed.

We now show that:

Indeed, either $d(a,u)=d(b,u)=0$, i.e., $a=u=b$, and thus $d(a,w_1)=d(u,w_1)=1=d(u,w_2)=d(b,w_2)$. Or, $d(a,u)=d(b,u)>0$, and thus $w_1$ is on the path from $u$ to $a$ on $P_1$, and $w_2$ is on the path from $u$ to $b$ on $P_2$. This implies $d(u,w_1)+d(w_1,a)=d(u,w_2)+d(w_2,b)$, and thus $d(w_1,a)=d(w_2,b)$.

Furthermore, applying Equation 5 on Equation 2 gives that:

Equation 6 and Equation 7 completes the proof of Claim 5. $\mathrm{⊲}$ This completes the proof of Theorem 2. $◀$

This structural result allows us to predict that every minimum isometric-universal graph of two trees $\{T_1,T_2\}$ either is a tree, or contains an isometric-universal graph for $\{T_1,T_2\}$ as a subgraph (only by removing edges). However, as the proof of Theorem 6 will explain, if we can compute a tree that contains $T_1$ and $T_2$ as subgraphs, then we can compute a minimum isometric-universal graph for $\{T_1,T_2\}$. More precisely:

Let $T_1,T_2$ be two trees with at most $n$ vertices. From Theorem 2, there always exists a minimum isometric-universal graph of two trees that is a tree itself. Thus, any algorithm that computes a minimum isometric-universal tree for $\{T_1,T_2\}$ computes a minimum isometric-universal graph for $\{T_1,T_2\}$ too.

In a tree there exists only one path connecting any pair of vertices. Thus, every tree that contains $T_1$ and $T_2$ as subgraphs (such a tree is called a supertree under graph isomorphism in [17]) is also an isometric-universal tree. According to Gupta and Nishimura [17, Theorem 9.6], a minimum supertree of two trees can be computed in time $O(n^{5/2}\log n)$.

From the above discussion, the minimum supertree for $T_1,T_2$ is a minimum isometric-universal tree and also a minimum isometric-universal graph for $\{T_1,T_2\}$, which concludes the proof. $◀$

This is a direct application of Theorem 1 applied on two forests, composed respectively of $s$ and $r$ trees. In the complexity formula of Theorem 1, we can bound $r$, $s$, and $f(n)$ as follows:

• $\mathrm{■}$

  $s⩽r⩽n$.

• $\mathrm{■}$

  $f(n)=C{n}^{5/2}{\log }_{2}n$, for some constant $C>0$, since, from Theorem 6, the time complexity of finding a minimum isometric-universal graph of two trees is at most $f(n)$. Note that $f$ is superlinear.

We have:

$r\min \{f(2n),sf(n)\}+s\min \{r\sqrt{s}\log n,rs+s\log \log s\}$

Applying Theorem 1, this completes the proof. $◀$

It is not difficult to see that this problem is in NP. We use a reduction from the 3D-Matching problem that is NP-complete even if each element is contained in at most three sets (see [14, Problem SP1 in Appendix A.3.1]). This restriction can be seen as determining a perfect matching in a 3-partite sub-cubic hypergraph.

For the 3D-Matching problem, we are given three disjoint sets $X,Y,Z$ of size $n$, and a set of triples $T\subseteq X\times Y\times Z$. We ask whether there exists or not a subset of $n$ triples of $T$ that are pairwise independent. In other words, a solution for the problem, called matching, is a subset $M\subseteq T$ of size $n$ such that no two triples of $M$ agree in any coordinate.

In order to encode the 3D-Matching problem into our problem, consider a instance $(X,Y,Z,T)$ where each element of $X,Y$, or $Z$ is contained in two or three triples⁵⁵5Clearly, any element has to appear at least once in $T$, and if it appears only once, then we have to take it in any solution, and so reducing the instance. of $T$. We have $|X|=|Y|=|Z|=n$ and $|T|\in \{2n,\mathrm{\dots },3n\}$, so that the instance is of size $O(n)$.

We construct a family $ℱ=\{F^X,F^Y,F^Z\}$ composed of three forests, each with $n$ trees, one tree for each element of $X$, $Y$, and $Z$. More precisely, for each set $W\in \{X,Y,Z\}$, the set of connected components of $F^W$ is denoted by $\{F(w):w\in W\}$, where $F(w)$ is the tree associated with the element $w\in W$ of the forest $F^W$. Each tree $F(w)$ will be described precisely hereafter.

For every $w\in \{1,\mathrm{\dots },2n\}$, let $S(w)$ be a subdivided star obtained from a $K_{1,3w+3}$ whose three of its edges have been replaced by a path of length $2n+2-w$. Let $𝒮=\{S(1),\mathrm{\dots },S(2n)\}$ be the collection of all such stars that are pairwise non-isomorphic. See Figure 8 for examples of such stars.

It is easy to check that:

For convenience, we will assume that $Y=\{1,\mathrm{\dots },n\}$ and $Z=\{n+1,\mathrm{\dots },2n\}$, so that $Y\cup Z=\{1,\mathrm{\dots },2n\}$. Actually, any one-to-one mapping from $Y\cup Z$ to $\{1,\mathrm{\dots },2n\}$ is fine. For each $w\in Y\cup Z$, the tree $F(w)$ is composed of a copy of the star $S(w)\in 𝒮$ where is attached a claw, i.e., a copy of a $K_{1,3}$. More precisely, the center of $S(w)$ is merged with a leaf of the claw. The tree $F(w)$ has $|V(S(w))|+|V(K_{1,3})|-1=3n+4$ vertices, and pathwidth two. See Figure 9.

Consider any $x\in X$, and define $T(x)=\left\{(x,y,z)\in T\right\}$ to be the set of triples of $T$ containing element $x$. From the restriction of the input, $|T(x)|\in \{2,3\}$.

Let us denote by $y_1,\mathrm{\dots },y_t$ and $z_1,\mathrm{\dots },z_t$ the elements of $Y$ and $Z$ that are contained in the triples of $T(x)$, where $t=|T(x)|$. The tree $F(x)$ of the forest $F^X$ is obtained from the copies of the $2t$ stars $S(y_1),\mathrm{\dots },S(y_t),S(z_1),\mathrm{\dots },S(z_t)$ where their centers are connected by a path in which each edge is alternatively replaced by a path of length two or three. Furthermore, along the path, the $2t$ star centers are encountered in the specific order $S(y_1)-\circ -S(z_1)-\circ -\circ -S(z_2)-\circ -S(y_2)$ if $t=2$ (dashes mean edges), and in the order $S(y_1)-\circ -S(z_1)-\circ -\circ -S(z_2)-\circ -S(y_2)-\circ -\circ -S(y_3)-\circ -S(z_3)$ if $t=3$. See Figure 10 with the notation therein.

Clearly, $F(x)$ is a tree of pathwidth two. Since each star $S(w)$ has $3n+1$ vertices (cf. Claim 12), the number of vertices of $F(x)$ is $|V(F(x))|=2t\cdot (3n+1)+3t-2=6tn+5t-2\in \{12n+8,18n+13\}$ depending on $t$. By construction, we have $|V(F^X)|={\sum }_{x\in X}\left|V\left(F(x)\right)\right|$.

An important property of $F(x)$ is that if $(x,y,z)\in T$, then a copy of the stars $S(y)$ and $S(z)$ appears as an isometric subgraph of $F(x)$. However, neither $F(y)$ nor $F(z)$ can appear in $F(x)$ as an isometric subgraph because of their claws. Another important property is that if $(x,y,z)\notin T$, then the stars $S(y)$ and $S(z)$ cannot appear consecutively in the main path of $F(x)$ (if they appear). This is due to the specific order of the stars along the path. In that case, the distance between their centers is at least 5.

Let $𝒰$ be any minimum isometric-universal graph for $ℱ=\{F^X,F^Y,F^Z\}$. We note that $ℱ$ has polynomial size w.r.t. the instance $(X,Y,Z,T)$, since each of the forests $F^X,F^Y,F^Z$ is composed of $n$ trees with $O(n)$ vertices each.

Each component of $𝒰$ must contain the trees $F(x)$, $F(y)$ and $F(z)$ for some elements $x,y,z$. In a favorable case, this component is composed of $F(x)$ plus only one single vertex. Indeed, if $y,z$ are both contained in $T(x)$, then $S(y)$ and $S(z)$ each appears in $F(x)$. It follows that $F(y)$ and $F(z)$ will almost fit in $F(x)$ but for one vertex of their claw. The only way to pack in $F(x)$ using one extra vertex is to share this vertex with their claw by being consecutive on the main path of $F(x)$. This favorable situation will occur simultaneously on each $F(x)$ if $(X,Y,Z,T)$ has a solution, i.e., if $T$ contains a matching for $X\times Y\times Z$. Unfortunately, if $y$ or $z$ are not in $T(x)$, and still want to pack in $F(x)$, then the resulting component would contain more than one vertex more as in $F(x)$. This situation will necessarily occur if $(X,Y,Z,T)$ has no solution. Overall, the number of vertices in $𝒰$ will allow us to determine whether a solution exists or not for $(X,Y,Z,T)$.

More formally, our goal is to prove the following claim:

The proof of this claim is available in the full version [3]. $◀$