Natural Calamities Demand More Rescuers: Exploring Connectivity Time Dynamic Graphs

[33] The Connectivity Time of a dynamic graph $G=(V,E)$ is the minimum integer $T\in \mathbb{N}$ such that $\forall$ $r\in \mathbb{N}\cup \{0\}$, the union graph $G_{r,T}:=(V,{\bigcup }_{i=r}^{r+T-1}E(i))$ is connected.

This model generalizes $T$-Interval Connectivity, but unlike $T$-Interval Connectivity, it allows temporary disconnections. Thus, Connectivity Time is strictly weaker than $T$-Interval Connectivity. In the next section, we discuss the model and problem definition.

We consider a dynamic network modeled as a sequence of undirected graphs $G=(V,E)$, where the node set $V$ remains fixed over time and satisfies $|V|=n$. Define $S=\{(u,v)|u,v\in V\}$ as the set of all possible edges, and let $𝒫(S)$ denote its power set. The function $E:\mathbb{N}\to 𝒫(S)$ maps each round number $r\in \mathbb{N}\cup \{0\}$ to the set of edges $E(r)$ present at that round, yielding the snapshot graph ${𝒢}_r=(V,E(r))$. The dynamic graph $G$ is thus given as a sequence $⟨{𝒢}_0,{𝒢}_1,{𝒢}_2,\mathrm{\dots }⟩$. We assume the presence of a dynamic adversary that may insert or delete any edge at the beginning of each round. The degree of a node $v$ at round $r$ is denoted by ${\mathrm{deg}}_r(v)$. The diameter of ${𝒢}_r$ is denoted by $D_r$.

Each snapshot graph ${𝒢}_r$ is unweighted, undirected, and anonymous. Moreover, the graph is port-labelled: for any node $v\in {𝒢}_r$, the incident edges are assigned distinct local port numbers in the range $[0,{\mathrm{deg}}_r(v)-1]$. For an edge $(u,v)$, the port numbers at $u$ and $v$ are independently assigned and unrelated. Port labellings can differ across rounds; i.e., port numbers at a node in ${𝒢}_r$ may not match those in ${𝒢}_{r^{\prime }}$ for $r\ne r^{\prime }$. Nodes do not have any storage capability. A node is referred to as hole in round $r$ if no agent is present at that node, and as multinode if two or more agents occupy it at round $r$. In this work, the graph $G(=⟨{𝒢}_0,{𝒢}_1,{𝒢}_2,\mathrm{\dots }⟩)$ maintains the Connectivity Time property for some $T$, i.e., for every $r\ge 0$, the graph $G_{r,T}:=(V,{\bigcup }_{i=r}^{r+T-1}E(i))$ is connected.

We consider $\mathrm{\ell }$ mobile agents that are initially placed arbitrarily on the nodes of $G$. Each agent has a unique identifier from the range $[1,n^c]$, where $c$ is some constant, and knows only its own ID. Agents are equipped with $O(\log n)$ memory and execute the algorithm under a fully synchronous scheduler, i.e., in each round $t$, every agent executes a Communicate-Compute-Move (CCM) cycle:

• $\mathrm{■}$

  Communicate: Agents communicate as per the communication model.

• $\mathrm{■}$

  Compute: Based on its local view and any received information, the agent performs computation, including deciding whether and where to move.

• $\mathrm{■}$

  Move: The agent moves through a chosen port or stays idle.

The time complexity is measured by the number of synchronous rounds. We refer to ${𝒢}_r$ together with the agents’ positions as the configuration. With a slight abuse of notation, we may denote the configuration at round $r$ by ${𝒢}_r$.

We adopt a standard visibility framework where agents have $l$-hop visibility. In the $l$-hop model [1, 34], at the beginning of round $r$, an agent can see the subgraph induced by nodes within distance $l$ from its current location in ${𝒢}_r$, including the presence or absence of agents in that neighbourhood. When $l=D_r$, this provides full visibility at round $r$.

In this work, we consider the global communication model [20, 8, 36, 30, 31]. The global communication allows agents to exchange messages with any agent located in the same connected component of ${𝒢}_r$, utilizing the graph’s links. The global communication between two different connected components of ${𝒢}_r$ is not possible, as there is no edge between two different connected components.

A node $v$ is visited by round $r$ if at least one agent is at node $v$ at round $t$, where $t\in [0,r]$. An algorithm achieves exploration if every node is visited at least once. And, an algorithm achieves perpetual exploration if every node is visited infinitely often.

While there remains a non-empty set of unexplored nodes, the goal is to transfer agents from explored and occupied nodes to those unexplored ones. As it can be difficult to differentiate between an unexplored node with an explored but unoccupied node, the algorithm may require to transfer agents from explored and occupied nodes to explored but currently unoccupied nodes as well. If an algorithm succeeds in keeping all explored nodes occupied, then eventually, as the adversary must pick an edge across the cut, some agent will move to an unexplored node and hence the node becomes visited. However, the adversary is powerful: if $b$ agents move from a node with $x$ agents to a node with agents according to some deterministic algorithm, making the new counts $y^{\prime }=y+b$ and $x^{\prime }=x-b$, the adversary can flip the roles of these two nodes in the next graph instance, effectively undoing progress as the algorithm performs the reverse operation. The proofs formalize this idea: with fewer than $(n-1)(n-2)/2+1$ agents, the adversary can always choose such a flip whereas with that many agents it cannot always do that.

Let $𝒏\mathbf{=}\mathrm{𝟐}𝒌$ for some $k\in \mathbb{N}$, $n\ge 4$ and $T\ge 2$. We give an initial configuration with $\frac{(n-2)(n-1)}{2}$ agents such that the exploration is impossible to solve. Let $v_1$, $v_2$, …, $v_n$ be nodes. At the beginning of round 0, consider $k$ many one length paths as follows: $P_1(=v_1\sim v_2)$, $P_2(=v_3\sim v_4)$, …, $P_{k-1}(=v_{n-3}\sim v_{n-2})$ and $P_k(=v_{n-1}\sim v_n)$. Let ${\alpha }_r(w)$ represent the number of agents located at a node $w$ at the beginning of round $r$, and let ${\beta }_r(w)$ represent the number of agents located at the node $w$ at the end of round $r$.²²2The parameter ${\beta }_r(w)$ is the number of agents at node $w$ after completing CCM cycle at round $r$. Let ${\alpha }_0(v_i)=n-i-1$ for $i\in [1,n-2]$, and ${\alpha }_0(v_{n-1})={\alpha }_0(v_n)=0$ (i.e., nodes $v_{n-1}$ and $v_n$ are holes). Let’s denote this configuration by ${𝒞}_0$ (refer to Fig. 1). The total number of agents is ${\sum }_{i=1}^n{\alpha }_0(v_i)={\sum }_{i=1}^{n-2}i=\frac{(n-2)(n-1)}{2}$. In round $r\ge 0$, the adversary maintains ${𝒢}_r$ as follows:

1. (a)

   $𝒓\mathbf{\in }\mathbf{[}\mathrm{𝟎}\mathbf{,}𝑻\mathbf{-}\mathrm{𝟐}\mathbf{]}\mathbf{:}$ It maintains ${𝒞}_0$ in these rounds.

2. (b)

   $𝒓\mathbf{\in }\mathbf{[}𝒊𝑻\mathbf{-}\mathrm{𝟏}\mathbf{,}\mathbf{(}𝒊\mathbf{+}\mathrm{𝟏}\mathbf{)}𝑻\mathbf{-}\mathrm{𝟐}\mathbf{]}$, where mod $\mathrm{𝟐}\mathbf{)}\mathbf{\ne }\mathrm{𝟎}$:

At round $iT-2$, there are $k$ many one length paths, say $P_1(=w_1\sim w_2)$, $P_2(=w_3\sim w_4)$, …, $P_{k-1}(=w_{n-3}\sim w_{n-2})$, $P_k(=w_{n-1}\sim w_n)$ (we separately show that nodes $w_{n-1}$ and $w_n$ are holes at round $iT-2$, with $w_n=v_n$). Note that at the end of round $T-2$, $w_i=v_i$, for every $i$. We can see ${𝒢}_{iT-2}$ in Fig. 2(A). Based on the movement of agents at round $iT-2$, the adversary forms $k$ paths, say $P_1^{\prime }$, $P_2^{\prime }$, …, $P_k^{\prime }$, at the beginning of round $iT-1$ as follows.

If ${\beta }_{iT-2}(w_1)\ge {\beta }_{iT-2}(w_2)$, then $P_1^{\prime }=w_1$. Else, $P_1^{\prime }=w_2$. For $j\in [2,k-1]$, $P_j^{\prime }$ is defined as follows.

If ${\beta }_{iT-2}(w_{n-3})\ge {\beta }_{iT-2}(w_{n-2})$, then $P_k^{\prime }=w_{n-2}\sim w_{n-1}\sim w_n$. Else, $P_k^{\prime }=w_{n-3}\sim w_{n-1}\sim w_n$. We can see ${𝒢}_{iT-1}$ in Fig. 2(B).

Without loss of generality, let $P_1^{\prime }(=w_1)$, $P_2^{\prime }(=w_2\sim w_3)$, …, $P_{k-1}^{\prime }(=w_{n-4}\sim w_{n-3})$, $P_k^{\prime }(=w_{n-2}\sim w_{n-1}\sim w_n)$. If ${\alpha }_{iT-1}(w_{n-2})=0$, the adversary maintains the graph ${𝒢}_r$ as ${𝒢}_{iT-1}$ for every $r\in [iT,(i+1)T-2]$. If ${\alpha }_{iT-1}(w_{n-2})>0$, the adversary maintains the graph ${𝒢}_r$ for every $r\in [iT,(i+1)T-2]$ as follows.

If an agent from node $w_{n-2}$ moves to node $w_{n-1}$ at round $r-1$, then adversary at the beginning of round $r$ maintains the following path: $P_1^{\prime }=w_1$, $P_2^{\prime }=w_2\sim w_3$,…, $P_{k-1}^{\prime }=w_{n-4}\sim w_{n-3}$, and $P_k^{\prime }=w_{n-1}\sim w_{n-2}\sim w_n$ (refer Fig. 3(A) at round $r-1$, and refer Fig. 3(B) at round $r$). Otherwise, it maintains the graph ${𝒢}_r$ as ${𝒢}_{r-1}$.

If an agent from node $w_{n-1}$ moves to node $w_{n-2}$ at round $r-1$, then adversary at the beginning of round $r$ maintains the following path: $P_1^{\prime }=w_1$, $P_2^{\prime }=w_2\sim w_3$,…, $P_{k-1}^{\prime }=w_{n-4}\sim w_{n-3}$, and $P_k^{\prime }=w_{n-2}\sim w_{n-1}\sim w_n$ (refer Fig. 4(A) at round $r-1$, and refer Fig. 4(B) at round $r$). Otherwise, it maintains the graph ${𝒢}_r$ as ${𝒢}_{r-1}$.

If $i=1$, then it is not difficult to observe that the number of agents at node ${\alpha }_{T-1}(w_{n-2})\le 1$ as ${\alpha }_{T-2}(x_{n-3})+{\alpha }_{T-2}(x_{n-2})=3$. We show later for every $i$, ${\alpha }_{iT-1}(w_{n-2})\le 1$. Thus, the way we change the graph, the agent always stays between node $w_{n-2}$ and $w_{n-1}$ and can not access node $w_n$ in round $r$. We denote this configuration by ${𝒞}_{1-2-3}$.

1. (c)

   $𝒓\mathbf{\in }\mathbf{[}𝒊𝑻\mathbf{-}\mathrm{𝟏}\mathbf{,}\mathbf{(}𝒊\mathbf{+}\mathrm{𝟏}\mathbf{)}𝑻\mathbf{-}\mathrm{𝟐}\mathbf{]}$, where mod $\mathrm{𝟐}\mathbf{)}\mathbf{=}\mathrm{𝟎}$:

At the end of round $iT-2$, there are $k$ many paths, say $P_1^{\prime }(=w_1)$, $P_2^{\prime }(=w_2\sim w_3)$, …, $P_{k-1}^{\prime }(=w_{n-4}\sim w_{n-3})$, $P_k^{\prime }=w_{n-2}\sim w_{n-1}\sim w_n$ (we separately show that nodes $w_{n-1}$ and $w_n$ are holes at the beginning of round $iT-2$, with $w_n=v_n$, and at most one agent occupy node $w_{n-2}$). We can see ${𝒢}_{iT-2}$ in Fig. 5(A). At round $iT-1$, the adversary forms $k$ many one length paths, say $P_1$, $P_2$, …, $P_k$. Based on the movement of agents at round $iT-2$, the adversary forms $k$ paths, say $P_1$, $P_2$, …, $P_k$, at the beginning of round $iT-1$ as follows.

If ${\beta }_{iT-2}(w_2)\ge {\beta }_{iT-2}(w_3)$, then $P_1=w_1\sim w_2$. Else, $P_1=w_1\sim w_3$. For $j\in [2,k-2]$, $P_j$ is defined as follows.

At the end of round $iT-2$, there is at most one agent in path $P_k^{\prime }$, and this agent is either at node $w_{n-2}$ or $w_{n-1}$ (we show this separately). If there is no agent in path $P_k^{\prime }$, then $P_{k-1}$ and $P_k$ are defined as follows. If ${\beta }_{iT-2}(w_{n-4})\ge {\beta }_{iT-2}(w_{n-3})$, then $P_{k-1}=w_{n-3}\sim w_{n-2}$ and $P_k=w_{n-1}\sim w_n$. Else, $P_{k-1}=w_{n-4}\sim w_{n-2}$ and $P_k=w_{n-1}\sim w_n$. If there is one agent in path $P_k^{\prime }$, then $P_{k-1}$ and $P_k$ are defined as follows. Based on agent’s position at node $w_{n-2}$ or $w_{n-1}$ at the end of round $iT-2$, the cases are as follows.

• $\mathrm{■}$

  If an agent is at node $w_{n-2}$ at the end of round $iT-2$, the path $P_{k-1}$ and $P_k$ are defined as follows. If ${\beta }_{iT-2}(w_{n-4})\ge {\beta }_{iT-2}(w_{n-3})$, then $P_{k-1}=w_{n-3}\sim w_{n-2}$ and $P_k=w_{n-1}\sim w_n$. Else, $P_{k-1}=w_{n-4}\sim w_{n-2}$ and $P_k=w_{n-1}\sim w_n$.

• $\mathrm{■}$

  If an agent is at node $w_{n-1}$ at the end of round $iT-2$, the path $P_{k-1}$ and $P_k$ are defined as follows. If ${\beta }_{iT-2}(w_{n-4})\ge {\beta }_{iT-2}(w_{n-3})$, then $P_{k-1}=w_{n-3}\sim w_{n-1}$ and $P_k=w_{n-2}\sim w_n$. Else, $P_{k-1}=w_{n-4}\sim w_{n-1}$ and $P_k=w_{n-2}\sim w_n$.

We can see ${𝒢}_{iT-1}$ in Fig. 5(B). It maintains ${𝒢}_r$ as ${𝒢}_{iT-1}$ for every $r\in [iT,(i+1)T-2]$. Later, we show that there is no agent in $P_k$, and one of the nodes in $P_k$ is $v_n$. We denote this configuration by ${𝒞}_{2-2}$.

Fig. 6 shows how the configuration evolves over time.

We define two notations as follows.

• $\mathrm{■}$

  (N1) $𝒓\mathbf{\in }\mathbf{[}𝒊𝑻\mathbf{-}\mathrm{𝟏}\mathbf{,}\mathbf{(}𝒊\mathbf{+}\mathrm{𝟏}\mathbf{)}𝑻\mathbf{-}\mathrm{𝟐}\mathbf{]}$, where mod $\mathrm{𝟐}\mathbf{)}\mathbf{=}\mathrm{𝟎}$ (or $𝒓\mathbf{\in }\mathbf{[}\mathrm{𝟎}\mathbf{,}𝑻\mathbf{-}\mathrm{𝟐}\mathbf{]}$): In this case, either configuration ${𝒞}_0$ or ${𝒞}_{2-2}$ is true. Therefore, at round $r$, there are $k$ one length paths $P_1$, $P_2$, …, $P_k$. Let $P_j(=w_{2j-1}\sim w_{2j})$, for every $j\in [1,k]$. If ${\alpha }_r(w_{2j-1})\ge {\alpha }_r(w_{2j})$, then we denote $w_{2j-1}$ as $w_{2j-1}^r$ and $w_{2j}$ as $w_{2j}^r$. Otherwise, we denote $w_{2j-1}$ as $w_{2j}^r$ and $w_{2j}$ as $w_{2j-1}^r$.

• $\mathrm{■}$

  (N2) $𝒓\mathbf{\in }\mathbf{[}𝒊𝑻\mathbf{-}\mathrm{𝟏}\mathbf{,}\mathbf{(}𝒊\mathbf{+}\mathrm{𝟏}\mathbf{)}𝑻\mathbf{-}\mathrm{𝟐}\mathbf{]}$, where mod $\mathrm{𝟐}\mathbf{)}\mathbf{\ne }\mathrm{𝟎}:$ In this case, configuration ${𝒞}_{1-2-3}$ is true. Therefore, at round $r$, there are $k$ paths $P_1^{\prime }$, $P_2^{\prime }$, …, $P_k^{\prime }$. Let $P_j^{\prime }(=w_{2j-2}\sim w_{2j-1})$, for every $j\in [2,k-1]$, $P_1^{\prime }(=w_1)$ and $P_k^{\prime }(=w_{n-2}\sim w_{n-1}\sim w_n)$. If ${\alpha }_r(w_{2j-2})\ge {\alpha }_r(w_{2j-1})$, then we denote $w_{2j-2}$ as $w_{2j-2}^r$ and $w_{2j-1}$ as $w_{2j-1}^r$. Otherwise, we denote $w_{2j-2}$ as $w_{2j-1}^r$ and $w_{2j-1}$ as $w_{2j-2}^r$. We consider $w_1$ as $w_1^r$, $w_{n-2}$ as $w_{n-2}^r$, $w_{n-1}$ as $w_{n-1}^r$, and $w_n$ as $w_n^r$.

Proving our lemma is equivalent to showing that the following two inequalities hold for every $j\in [1,k-1]$ at round $r$:

We use mathematical induction to prove inequalities (A) and (B) for every $r\ge 0$. Both inequalities are true for $r=0$ as ${𝒞}_0$ includes $k$ paths: $P_1(=v_1\sim v_2)$, $P_2(=v_3\sim v_4)$, …, $P_{k-1}(=v_{n-3}\sim v_{n-2})$, and an additional path $P_k(=v_{n-1}\sim v_n)$. We define ${\alpha }_0(v_i)=n-i-1$ for $i\in [1,n-2]$, with ${\alpha }_0(v_{n-1})={\alpha }_0(v_n)=0$. Therefore, $w_i^0=v_i$ for every $i\le n-2$.

Assuming the statement is true for round $r\ge 0$, we aim to show that it also holds for round $r+1$. There are five possible cases to consider: Case 1: $r,r+1\in [0,T-2]$, Case 2: $r,r+1\in [iT-1,(i+1)T-2]$, where $i$ is an odd number, Case 3: $r,r+1\in [iT-1,(i+1)T-2]$, where $i$ is an even number, Case 4: $r=iT-2$, where $i$ is odd, and Case 5: $r=iT-2$, where $i$ is even. Due to the length of the proof, we present only the proofs of Case 1 and Case 4 here. The proofs of Case 2 and Case 3 follow similar ideas to Case 1, and Case 5 builds upon the approach used in Case 4. The proof of Case 2, 3 and 5 is in Appendix, see Section A.2.

In this case, agents are in configuration ${𝒞}_0$ at round $r$ and $r+1$.

Due to the induction hypothesis, the following inequality holds:

Since the dynamic graph does not change between rounds $0$ and $T-2$, no matter how agents move, for every $j\in [1,k-1]$, we have the following:

Therefore, the following inequality holds using Eq. (1) and Eq. (2):

The inequality ${\alpha }_r(w_1^r)\ge n-2$ holds due to the induction hypothesis, and the inequality ${\alpha }_r(w_1^r)+{\alpha }_r(w_2^r)\ge (n-2)+(n-3)$ is valid due to proof of (A). Therefore, regardless of how the agents move in round $r$, we have ${\alpha }_{r+1}(w_1^{r+1})\ge n-2$ as ${\alpha }_r(w_1^r)+{\alpha }_r(w_2^r)={\alpha }_{r+1}(w_1^{r+1})+{\alpha }_{r+1}(w_2^{r+1})$ and ${\alpha }_{r+1}(w_1^{r+1})\ge {\alpha }_{r+1}(w_2^{r+1})$. This shows (B) holds for $j=1$. For $j\in [2,k-1]$, we use a contrapositive argument. Suppose for some smallest value $j\ge 2$, the inequality (B) does not hold for round $r+1$. Then the following inequality must be true:

Due to Eq. (3), we get:

Therefore, using Eq. (4) and Eq. (5), the inequality holds. Rewrite Eq. (3) as:

From Eq. (4) and Eq. (6), the inequality ${\alpha }_{r+1}(w_{2j}^{r+1})>n-2j$ holds. Thus, due to our assumption (i.e., Eq. 4), we have and ${\alpha }_{r+1}(w_{2j}^{r+1})>n-2j$. Therefore, we have . This leads to a contradiction because, due to (N1), the inequality ${\alpha }_{r+1}(w_{2j-1}^{r+1})\ge {\alpha }_{r+1}(w_{2j}^{r+1})$ holds. This shows that our initial assumption is incorrect. Therefore, inequality (B) holds for round $r+1$.

In this case, at round $r=iT-2$, where $i$ is an odd number, the configuration is either ${𝒞}_0$ or ${𝒞}_{2\text{-}2}$, and at round $r+1$, it changes to ${𝒞}_{1-2-3}$

Due to the induction hypothesis, the following inequality is true:

The adversary constructs the dynamic graph in round $r+1$ based on the agents’ positions at the end of round $r$. Let $p=\text{max}\{{\beta }_r(w_{2j-1}^r),{\beta }_r(w_{2j}^r)\}$. Therefore, ${\alpha }_{r+1}(w_{2j-1})=p$ and the value of ${\alpha }_{r+1}(w_{2j})$ is as follows (recall configuration ${𝒞}_{1-2-3}$):

The adversary forms the dynamic graph at round $iT-1$, ensuring the following equality:

Using Eq. (9), the following equality holds.

Due to Eq. (8), we have ${\alpha }_{r+1}(w_{2j}^{r+1})\ge {\alpha }_r(w_{2j-1}^r)+{\alpha }_r(w_{2j}^r)-p$. Thus, using Eq. (10):

Using Eq. (7) and Eq. (11), the inequality (A) holds for round $r+1$.

For $j=1$, the inequality ${\alpha }_r(w_1^r)\ge n-2$ holds, and due to the proof of (A), the inequality ${\alpha }_r(w_1^r)+{\alpha }_r(w_2^r)\ge n-2+n-3$ holds. Therefore, ${\alpha }_{r+1}(w_1^{r+1})\ge n-2$ holds regardless of how agents move at round $r$ due to the following reason. If , then and holds as per the dynamic graph construction at round $iT-1$, ${\alpha }_{r+1}(w_1^{r+1})=\text{max}\{{\beta }_r(w_1^r),{\beta }_r(w_2^r)\}$. Therefore, ${\beta }_r(w_1^r)\le n-3$ and ${\beta }_r(w_2^r)\le n-3$, and hence the inequality ${\beta }_r(w_1^r)+{\beta }_r(w_2^r)\le 2(n-3)$ holds. Since ${\beta }_r(w_1^r)+{\beta }_r(w_2^r)={\alpha }_r(w_1^r)+{\alpha }_r(w_2^r)$, the inequality ${\alpha }_r(w_1^r)+{\alpha }_r(w_2^r)\le 2(n-3)$. This leads to a contradiction as ${\alpha }_r(w_1^r)+{\alpha }_r(w_2^r)\ge n-2+n-3$. Therefore, our assumption is wrong, and it implies ${\alpha }_{r+1}(w_1^{r+1})\ge n-2$. Now we prove (B) when $j\ge 2$. Due to (A), the following inequalities hold for $j\ge 2$.

In Eq. (9), the lower bound of $p$ is $\lceil \frac{{\alpha }_r(w_{2j-1}^r)+{\alpha }_r(w_{2j}^r)}{2}\rceil$. Using Eq. (9), we have:

Using Eq. (12), we have (by taking the sum of inequalities of Eq. (12)):

Since $\lceil x\rceil \ge x$ for every $x\in ℝ$, the following holds: