Designing Sparse Temporal Graphs Satisfying Connectivity Requirements

Assume by contradiction that ${𝒯}_{\downarrow }[S]$ is not connected. Then, there exists a vertex $w$ such that deleting $w$ from ${𝒯}_{\downarrow }$ creates at least two connected components containing at least one vertex of $S$ each. Let $C_0,\mathrm{\dots },C_{\mathrm{\ell }}$ be the connected components obtained by deleting $w$. For $j\in [0,\mathrm{\ell }]$, we denote $(\{w,s_j\},t_j)$ the temporal edge connecting $w$ to $C_j$ in $𝒯$. Without loss of generality, assume that . As $W$ is a closed walk, we have that there exists $i\in [0,k-1]$ such that $u_i\in C_p$ and $u_{i+1}\in C_q$ with . As $(u_i,u_{i+1})\in R$ and the only path from $u_i$ to $u_{i+1}$ in ${𝒯}_{\downarrow }$ contains the edge $\{w,s_p\}$ followed by the edge $\{w,s_q\}$, we must have .

$◀$

Note that having the arcs $(u,v)$ and $(v,u)$ in the connected request graph implies that the edge $\{u,v\}$ must be in the footprint of any tree solution. In the following, we will call such an edge $\{u,v\}$ a forced edge. Another direct consequence of this lemma is the following:

Lemma 11 leads to a rather natural definition of what we call a tree representation.

Note that the footprint of a tree solution for a request graph $R$ is always a tree representation of $R$. One could hope that having a tree representation of a request graph $R$ is equivalent to having a tree solution for MinCRS. However, this is not the case. Indeed, consider the request graph $R=(V,A)$ depicted in Figure 4. Any tree on $V$ with edges $\{a,b\}$, $\{b,c\}$, $\{c,d\}$, $\{d,e\}$ and an edge between $f$ and any other node is a tree representation of $R$. Now, if a tree solution exists for MinCRS, it must contain the edges $\{a,b\}$, $\{b,c\}$, $\{c,d\}$ and $\{d,e\}$, as they are forced edges. If the last edge is between $f$ and $a$, $b$ or $c$, the time appearance on the edge $\{e,d\}$ must be smaller than the one on $\{d,c\}$ in order to satisfy the request from $e$ to $f$ in $R$. However, the request from $c$ to $e$ in $R$ enforces the time appearance on the edge $\{e,d\}$ to be greater than the one on $\{d,c\}$. By symmetry, we conclude that it is also not possible to have the edge between $f$ and $d$ or $e$. Thus, there is no tree solution for MinCRS.

However, we will prove that, when the request graph is strongly connected, having a tree representation is equivalent to having a tree solution for MinCRS.

Let $H_R$ be the closed walk hypergraph of $R$.

$\Rightarrow$: We show that $R$ being walk-Helly implies that $L(H_R)$ is chordal. Let $C=(E_1,\mathrm{\dots },E_k,E_1)$ be a cycle in $L(H_R)$ with $k\ge 4$ and such that $C$ does not have a chord. Recall that $E_i$ is a set of vertices that forms a closed walk in $R$ (with a slight abuse of notation, we use $E_i$ to denote the vertex of $L(H_R)$ but also the associated hyperedge in $H_R$). Let $S={\bigcup }_{i\in [3,k]}{E}_i$. By concatenating the closed walks $E_3,\mathrm{\dots },E_k$ (possible as $E_i$ intersects $E_{i+1}$ for each $i\in [3,k-1]$), we obtain a closed walk $W=(u_1,\mathrm{\dots },u_{\mathrm{\ell }})$ in $R$ with $\{u_1,\mathrm{\dots },u_{\mathrm{\ell }}\}=S$. First, we have $E_1\cap E_2\ne \mathrm{\varnothing }$. As $E_1\cap E_k\ne \mathrm{\varnothing }$, we have $E_1\cap S\ne \mathrm{\varnothing }$ and as $E_2\cap E_3\ne \mathrm{\varnothing }$, we have $E_2\cap S\ne \mathrm{\varnothing }$. As $H_R$ is Helly, $E_1\cap E_2\cap S\ne \mathrm{\varnothing }$. Let $s\in E_1\cap E_2\cap S$. There exists $i\in [3,k]$ such that $s\in E_i$. Let us take such a $i$ that is minimal. If $i\ne 3$, we have that $s\in E_2\cap E_i$, and thus there is an edge between $E_i$ and $E_2$ in $L(H_R)$, contradicting the fact that $C$ has no chord. If $i=3$, we have that $s\in E_1\cap E_i$, which again gives us a chord between $E_1$ and $E_i$ in $C$. Thus, we have that $H_R$ is Helly and $L(H_R)$ is chordal. By Theorem 19, $H_R$ is a hypertree, that is there exists a tree representation of $R$.

$\Leftarrow$: We have that $H_R$ is a hypertree. By Theorem 19, we thus have that $H_R$ is Helly, that is $R$ is walk-Helly. $◀$

Let us now prove the equivalence between statements 1 and 3 of Theorem 20. First, statement 3 trivially implies statement 1 (here again, the strong connexity of $R$ is not required).

Let $𝒯$ be such a tree solution. In particular, thanks to Lemma 11, ${𝒯}_{\downarrow }$ is a tree representation of $R$, that is to say the closed walk hypergraph $H_R$ of $R$ is a hypertree. Thus, by Theorem 19, $R$ is walk-Helly. $◀$

Finally, let us prove that statement 1 implies statement 3, which is the core of the demonstration. The proof will consist of three steps:

• $\mathrm{■}$

  We introduce the notion of authorized arc and show that adding an authorized arc to a strongly connected request graph that is walk-Helly preserves the walk-Helly property (Lemma 25).

• $\mathrm{■}$

  We show that, as long as there are not $n-1$ forced edges, we can find an authorized arc that is not in the request graph $R$, if $R$ is walk-Helly (Lemma 27).

• $\mathrm{■}$

  We finally show that, when having $n-1$ forced edges in a request graph that is walk-Helly, we can assign labels to the forced edges in order to obtain a tree solution for MinCRS (Lemma 28).

Let $R$ be a connected request graph. In the following, we will write $P(a,b,\overline{c})$ to denote the existence of a path from $a$ to $b$ that does not contain $c$ in $R$, and $W(a,b,\overline{c})$ to denote the existence of a closed walk containing $a$ and $b$ but not $c$ in $R$, for $a,b,c$ vertices of $R$. We say that an arc $(u,v)$ is authorized if for every vertex $x$ of $R$ we do not have both $W(u,x,\overline{v})$ and $W(v,x,\overline{u})$.¹¹1Note that if an arc $(u,v)$ is not authorized, then the edge $\{u,v\}$ cannot be part of a tree solution. Indeed, having the edge in a tree solution would contradict Lemma 11 as we have $W(u,x,\overline{v})$ and $W(v,x,\overline{u})$ for some $x$.

We first show that if $R$ is strongly connected and walk-Helly, then adding an authorized arc to $R$ preserves the property of being walk-Helly. For instance, we have that the strongly connected request graph $R$ of Figure 6 is walk-Helly and adding the authorized arc $(a,b)$ preserves the walk-Helly property. Due to space constraints, the proof of this lemma is omitted here; It can be found in [4].

The general idea of the algorithm that builds a tree solution if it exists is to find an authorized arc $(u,v)$ that is not in $R$ and add the arcs $(u,v)$ and $(v,u)$ to $R$ until there are $n-1$ forced edges forming a tree. Note that we can add both the arcs $(u,v)$ and $(v,u)$ as if $(u,v)$ is authorized, then $(v,u)$ is also authorized, and adding the arc $(u,v)$ to $R$ does not change the fact that $(v,u)$ is authorized by definition of an authorized arc. The following lemma shows that, as long as we do not have $n-1$ forced edges forming a tree, we can find an authorized arc $(u,v)$ when $R$ is walk-Helly.

Let $T$ be a tree representation of $R$ (exists as $R$ is walk-Helly and by Proposition 22) and let $\{u,v\}$ be an edge of $T$ that is not a forced edge in $R$. We have that $(u,v)$ or $(v,u)$ (or both) are not in $R$. Without loss of generality, let us assume that $(u,v)$ is not in $R$ and let us show that the arc $(u,v)$ is authorized. If $(u,v)$ is not authorized, there exists a vertex $x$ such that $W(u,x,\overline{v})$ and $W(v,x,\overline{u})$ in $R$. Consider the request graph $R^{\prime }$ which is $R$ to which we add the arcs $(s,t)$ and $(t,s)$ for each edge $\{s,t\}$ of $T$ (if not already in $R$). We have that $T$ is a tree representation of $R^{\prime }$, so $R^{\prime }$ is walk-Helly by Proposition 22. However, we have $W(u,x,\overline{v})$ and $W(v,x,\overline{u})$ in $R^{\prime }$ and also the closed walk consisting of the arc $(u,v)$ and the arc $(v,u)$ in $R^{\prime }$, contradicting the fact that $R^{\prime }$ is walk-Helly. $◀$

We finally show that, when we have $n-1$ forced edges forming a tree, we can assign labels to the tree in order to obtain a solution for MinCRS if the request graph $R$ is walk-Helly. An illustration of the construction is given in an example after the proof. In Figure 7 the left part represents the request graph, and the right part represents a tree solution with labels (the middle part illustrates part of the proof).

For a forced edge $\{u,v\}$, we denote $t_{\{u,v\}}$ the appearance time that we will give to this edge. First, observe that each arc $(u,v)\in R$ such that $\{u,v\}$ is not a forced edge enforces an order on the appearance times of the edges on the path from $u$ to $v$ in $T$. More precisely, let $P=(u_0=u,u_1,\mathrm{\dots },u_k=v)$ be the unique path from $u$ to $v$ in $T$ and let $e_i=\{u_i,u_{i+1}\}$ for $i\in [0,k-1]$. Then, we must have .

Let us construct the following digraph $D$. For each forced edge $e$ of $R$, we have a vertex $v_e$ in $D$. For each arc $(u,v)\in R$ such that $\{u,v\}$ is not a forced edge, let $P=(u_0=u,u_1,\mathrm{\dots },u_k=v)$ be the path from $u$ to $v$ in $T$ and $e_i=\{u_i,u_{i+1}\}$. Then, we put an arc from $v_{e_i}$ to $v_{e_{i+1}}$ in $D$ for $i\in [0,k-2]$. Note that having an arc from $v_e$ to $v_{e^{\prime }}$ in $D$ means that $e$ and $e^{\prime }$ are sharing an endpoint in $T$ and that we must have . If there is no closed walk in $D$, then assigning labels to the forced edges by following a topological order of $D$ ensures that the obtained temporal graph is a solution.

Now, let us assume that there exists a closed walk in $D$. Let $W=(v_{e_0},v_{e_1},\mathrm{\dots },v_{e_k}=v_{e_0})$ be such a closed walk with minimal length. Let us show that all forced edges $e_i$ for $i\in [0,k-1]$ share a common endpoint in $T$. First, we have that $e_0$ and $e_1$ shares an endpoint, that we will denote $s$. Now, let us assume that all forced edges $e_i$ for $i\in [0,j]$ have $s$ as one endpoint, for $1\le j\le k-3$. We have that $e_{j+1}$ and $e_j$ have a common endpoint. Assume that this is not $s$. Then there exists a path in $T$ consisting of the edges $e_{j+1}$, $e_j$ and $e_0$ in this order. However, we have a path from $v_{e_{j+1}}$ to $v_{e_0}$ in $D$ and as there exists an arc from a vertex associated with a forced edge to another in $D$ only between forced edges sharing an endpoint, we have that $v_{e_j}$ should be in every path from $v_{e_{j+1}}$ to $v_{e_0}$ in $D$, contradicting the minimality of $W$. Finally, $e_{k-1}$ shares an endpoint with $e_0$ and also with $e_{k-2}$ in $T$, which is thus $s$.

Let $e_i=\{s,w_i\}$ for $i\in [0,k-1]$ and let $T_i$ be the subtree containing $w_i$ obtained when deleting vertex $s$ of $T$. As $(v_{e_i},v_{e_{i+1}})$ is an arc of $D$ for $i\in [0,k-1]$, there exists an arc in the request graph $R$ from a vertex $s_i\in T_i$ to a vertex $t_{i+1}\in T_{i+1}$. Also, there exists a path in $R$ from $t_i$ to $s_i$ for $i\in [1,k-1]$ (resp. from $t_k$ to $s_0$) obtained by following the path from $t_i$ to $s_i$ in $T_i$ (resp. from $t_k$ to $s_0$ in $T_0$). Concatenating those paths with the arcs from $s_i$ to $t_{i+1}$ gives a closed walk in $R$ that contains all $s_i$ and $t_i$ (and potentially other vertices) but that does not contain $s$. This contradicts the fact that $T$ is a tree representation of $R$. $◀$

From this proof, we can directly derive a polynomial time algorithm, called Labelisation, such that, given a connected request graph $R$ with $n-1$ forced edges, it assigns appearance times to the forced edges so that the resulting temporal graph is a solution for MinCRS, or outputs NO if it is not possible.

We can now conclude the proof of Theorem 20 by showing that statement 1 implies statement 3.

Let $R$ be a strongly connected request graph that is walk-Helly. If there are $n-1$ forced edges, then Lemma 28 shows that we can assign appearance times to the edges of the tree formed by the forced edges so that it is a tree solution for MinCRS. If there are not yet $n-1$ forced edges, we can find an authorized arc $(u,v)$ not in $R$ by Lemma 27, and add the arcs $(u,v)$ and $(v,u)$ in $R$ while maintaining the walk-Helly property by Lemma 25. Note that if $R$ is not walk-Helly, then there exists no tree solution for MinCRS by Proposition 23 and the algorithm will return NO either because there are not $n-1$ forced edges after adding the authorized arcs to $R$, or because the labelisation will fail. Thus, Algorithm 1 computes a tree solution if it exists in polynomial time. $◀$