Restless Exploration and Token Dissemination in Vertex-Permuted Temporal Graphs

If $|I|=|N(I)|$, then the lemma follows trivially, since $I$ is the blocking set. If $|I|>|N(I)|$, we prove the claim by giving a simple iterative procedure to find such a subset.

While $|I|>|N(I)|$, remove an arbitrary vertex from $I$ and update $N(I)$. At each step, the size of $I$ decreases by 1, while the size of $N(I)$ does not increase. Since $G$ is connected, $N(I)$ is never empty, ensuring that the process terminates with $|I|=|N(I)|>0$, where $I$ is the required blocking set. This concludes the proof. $◀$

Figure 6 illustrates an example of this procedure: $I$ is an independent set with 5 vertices, and $N(I)$ is set of neighbors of vertices in $I$. Since $|I|>|N(I)|$, we start by removing vertex $1$ from $I$, which causes the removal of vertices $a$ and $b$ from $N(I)$. The updated sets are $I=\{2,3,4,5\}$ and $N=\{c,d\}$. In the next step, we remove vertex $2$ from $I$ but $N(I)$ remains unchanged since $c$ and $d$ have other neighbors in $I$. Similarly, removing vertex $3$ does not alter $N(I)$. At this point, the process terminates with $|I|=|N(I)|$, forming a blocking set. Note that selecting different vertices during the steps may lead to different blocking sets.

Let . Denote $TH(G^{\mathrm{\Pi }},s,t)$ as $H_t$ and let $N_t=N(H_t)$. So the set of vertices that are holders as well as neighbors of holders is $H_t\cap N_t$. Denote $H_t^{\prime }=H_t-N_t$ and $N_t^{\prime }$ to be the set of neighbors of vertices in $H_t^{\prime }$, that is $N_t^{\prime }=N(H_T^{\prime })$. See Figure 7 for an illustration.

Observe that $H_t^{\prime }$ is an independent set. We claim that $H_t^{\prime }$ is not empty. If instead, every vertex in $H_t$ is also a neighbor of a vertex in $H_t$, all these vertices will also be token holders in time step $t+1$. Since the graph is connected, and since , at least one more vertex will also be token holder at time $t+1$, implying that $NoT(t+1)>NoT(t)$, a contradiction. This proves the claim.

Next, consider $N_t^{\prime }$, the set of neighbors of $H_t^{\prime }$. Observe that $N_t^{\prime }$ is not empty, if so, $H_t^{\prime }$ would be disconnected from the rest of the graph. Also clearly $N_t^{\prime }\cap H_t=\mathrm{\varnothing }$. We claim that $|H_t^{\prime }|\ge |N_t^{\prime }|$. Suppose instead that . Consider the token holders at time $t+1$. Every node (if any) in $H_t\cap N_t$ will be a token holder at time $t+1$. Also all nodes in $N_t^{\prime }$ will be token holders at time $t+1$. Therefore

a contradiction to $NoT(G^{\mathrm{\Pi }},s,t+1)\le NoT(G^{\mathrm{\Pi }},s,t)$.

Therefore $|H_t^{\prime }|\ge |N_t^{\prime }|\ge 1$ as claimed. $◀$

In the token dissemination procedure for any VPG based on $G=(V,E)$, unless there is a blocking set in $G$ , the number of vertices that have received a token increase in every time step until the number of token holders is $|V|$. Lemma 7 formalizes this observation.

Follows from Lemmas 5 and 6. $◀$

From Lemma 7, we can deduce that if the graph $G(V,E)$ does not have a blocking set, then the number of token holders keeps increasing in every time step until it equals $|V|$. So $G$ is fully tokenizable. $◀$

An important observation in the token dissemination procedure for a graph $G=(V,E)$ with a MBS $S$ is as follows: the number of token holders continues to increase in every step until it reaches $|S|$; after this time step, the number of token holders will remain at least $|S|$ in all subsequent time steps. This behavior is formalized and proven in the following lemma.

For the first part, suppose as a contradictory assumption that there exists some $\mathrm{\Pi }$, $s$, and $t$ such that, , then from Lemma 7, there must exist a blocking set $S^{\prime }$ such that , which contradicts the assumption that the size of the minimum blocking set is $k$. Therefore, for every $\pi ,s,t$, if , it follows that $NoT(G^{\mathrm{\Pi }},s,t+1)>NoT(G^{\mathrm{\Pi }},s,t)$.

For the second part, suppose $NoT(G^{\mathrm{\Pi }},s,t)\ge k$ and . Once again, by Lemma 7, this would imply the existence of an MBS $S^{\prime }$ such that , which contradicts the assumption that the size of the MBS is $k$. $◀$

Building on the lemmas and observations established so far, we now present a characterization of untokenizable, partially tokenizable, and fully tokenizable graphs. The following theorems precisely describe the conditions under which a graph is untokenizable or partially tokenizable based on the properties of its MBS.

First we prove that if there is a MBS $S$ such that , then $G(V,E)$ is untokenizable. Let $N=N(S)$, and let $U=V-S-N$. We describe a sequence of permutations $\mathrm{\Pi }$ and a start vertex such that vertices in $U\subset V$ will never hold a token in $G^{\mathrm{\Pi }}$. Since $S$ is a MBS of $G$ and $|S|=k$, we have $|N|=k$ and $|U|=n-2k$. Wlog let $S=[0,k-1]$, $N=[k,2k-1]$, and $U=[2k,n-1]$. Our temporal graph will be a $2$-periodic graph such that in the odd time steps, we have the original graph $G$ and in the even steps we use the following permutation:

With this permutation $\mathrm{\Pi }$, observe that the subgraph induced by $U$ is not connected to $S$ in odd steps, and is not connected to vertices in $N$ in even steps. To prevent $U$ from ever obtaining a token, it is sufficient to start the token procedure at some vertex $s$ in $S$. Then in time step $2$, a subset of the vertices in $N$ will hold the token, and none of the vertices in $U$ have the token. Since the subgraph induced by $U$ is not connected to any vertex in $N$ in time step 2, there is no way for the vertices in $U$ to become token holders in the following step. Inductively, it is straightforward to see that $TH(G^{\mathrm{\Pi }},s,t)\subseteq S$ for odd $t$ and $TH(G^{\mathrm{\Pi }},s,t)\subseteq N$ for even $t$. This ensures that none of the vertices in $U$ will ever hold a token, making the graph $G$ untokenizable.

Next we prove the other direction. Suppose that $G(V,E)$ with $n$ vertices is untokenizable. This means there exists an initial vertex $s$ and a sequence of permutations $\mathrm{\Pi }$ such that $HS(G^{\mathrm{\Pi }},s,n)\ne V$. This implies that the maximum number of token holders at any step must be some , and hence, there must exist some time step in which $NoT(G^{\mathrm{\Pi }},s,t)=k$ and $NoT(G^{\mathrm{\Pi }},s,t+1)\le NoT(G^{\mathrm{\Pi }},s,t)$. By Lemma 6, at time $t$, there there exists a non-empty independent set of token holders $H_t^{\prime }$ such that $|H_t^{\prime }|\ge |N(H_t^{\prime })|\ge 1$.

Furthermore, since $G$ is untokenizable, and therefore . By Lemma 5, $G$ has a blocking set of size as desired. $◀$

First, we will prove that if there exists a MBS  $S$ with $|S|=\frac{n}{2}$, then the graph is partially tokenizable. Since $|S|=\frac{n}{2}$, the graph is tokenizable by Theorem 10.

Now, let $S$ be the MBS , wlog let $S=[0,n/2-1]$. Our temporal graph will be a $2$-periodic graph; in odd steps, we have the original graph $G$, and in even steps, we use the permutation $\pi (i)=(i+n/2)modn$. Let $NoT(i)$ be the number of tokens in step $i$. By Lemma 9, $NoT(G^{\mathrm{\Pi }},s,t)$ keeps increasing until for some time step $t$ we have $NoT(G^{\mathrm{\Pi }},s,t)$$=|S|$. After this step, all vertices in the set $[0,n/2-1]$ are holders in odd steps, and all remaining vertices are holders in even steps and NoT$(G^{\mathrm{\Pi }},s,n)=\frac{n}{2}$. This proves that $G$ is partially tokenizable.

Conversely, suppose for graph $G$, there does not exist an MBS $S$ with $|S|=\frac{n}{2}$. Then either $G$ does not have a blocking set at all, or it has an MBS of size (since any blocking set has to be of size $\le \frac{n}{2}$). In the first case, by Theorem 8, $G$ is fully tokenizable, and in the second case, by Theorem 10, it is untokenizable. $◀$

If $G$ does not contain any BS, then by Lemma 8, $G$ is fully tokenizable. For the converse, assume for the purpose of contradiction that $G$ is fully tokenizable, and that $G$ contains a BS. Let $S$ be a MBS of $G$. Then either $|S|=\frac{n}{2}$ or .

• $\mathrm{■}$

  If $|S|=\frac{n}{2}$, then by Theorem 11, $G$ is partially tokenizable.

• $\mathrm{■}$

  If , then by Theorem 10, $G$ is untokenizable.

In both cases, $G$ is not fully tokenizable, a contradiction to the assumption. Therefore, $G$ does not contain a $BS$. $◀$

Suppose $G$ has no MBS of size . Then Theorems 12 and 11 imply that under any permutation sequence $\mathrm{\Pi }$, and from any start vertex, the token dissemination procedure will ensure that all vertices in $G^{\mathrm{\Pi }}$ become token holders in $|V|$ steps, ensuring restless token dissemination in $G^{\mathrm{\Pi }}$. Conversely, suppose there is a distributed algorithm for token dissemination in every vertex-permuted graph $G^{\mathrm{\Pi }}$ based on $G$. Fix a vertex-permuted graph $G^{\mathrm{\Pi }}$ based on $G$, and suppose there exists a schedule for restless token dissemination in $G^{\mathrm{\Pi }}$. It must be a subset of the schedule implied by our token dissemination procedure, in which every vertex sends the token to all its neighbors in the step immediately after it receives it. Therefore our token dissemination procedure will also ensure that tokens are restlessly disseminated to all vertices in $G^{\mathrm{\Pi }}$. Since this is true for every $G^{\mathrm{\Pi }}$ based on $G$, it follows that $G$ is tokenizable, and by Theorem 10, $G$ has no MBS of size . $◀$

We note that if $G$ has an MBS of size exactly $|V|/2$, there are VPGs based on $G$, in which the token will never be held simultaneously by all nodes in the restless setting, whereas if $G$ has no blocking set, then for every VPG $G^{\mathrm{\Pi }}$ based on $G$, the token dissemination procedure described in Section 3.1 results in every node simultaneously holding the token.

Suppose $G$ is tokenizable. Let $G^{\mathrm{\Pi }}$ be an arbitrary VPG based on the graph $G$, and of lifetime $L\ge n(n-1)$. By the definition of tokenizability, for every $s\in V$, $HS(G^{\mathrm{\Pi }},s,n)=V$. That is, for any vertex $u$, we have $u\in HS(G^{\mathrm{\Pi }},s,n)$. This implies that there exists a restless temporal walk from $s$ to $u$ in at most $n$ time steps. Using the standard technique of concatenating temporal walks between pairs of vertices into an exploration schedule, it follows that there is a restless exploration schedule of length at most $n(n-1)$ in $G^{\mathrm{\Pi }}$ starting at any vertex $s$.

Conversely, suppose $G$ is untokenizable. Then by Theorem 10, $G$ has an MBS $S$ of size . Similarly to the proof of Theorem 10, we define a 2-periodic VPG (of infinite lifetime) based on $G$, in which $G_i=G$ for odd $i$, and in even time steps, the vertices in $S$ change places with the vertices in $N(S)$. Let $v$ be an arbitrary vertex in $S$ and let $u$ be an arbitrary vertex in $V-\{S\cup N(S)\}$. Since , there exists at least one such $u$. It is clear that there is no temporal walk (of any length) from $v$ to $u$ in this graph. Therefore $G^{\mathrm{\Pi }}$ is unexplorable. $◀$

We note that the exploration schedule mentioned above can be constructed in an offline and centralized manner, and is not necessarily an optimal schedule; we only claim that a schedule of length at most $n(n-1)$ exists.