# Cover Time in Edge-Uniform Stochastically-Evolving Graphs +
## 6 An Exact Approach
The probability is also zero for all graph instances \(H_{j}\) where the possible edge is not alive, i.e., \(\{v,v^{\prime}\}\
ot\in E(H_{j})\). In contrast, if \(\{v,v^{\prime}\}\in E(H_{j})\), then \(\Pr[v\stackrel{{ H_{j}}}{{\rightarrow}}v^{\prime}]=|N_{H_{j}}(v) |^{-1}\), since the agent chooses a destination uniformly at random out of the currently alive ones. Finally, if \(v=v^{\prime}\), then the agent remains still, with probability one, only if there exist no alive incident edges. We summarize the above facts in the following equation: \[\Pr[v\xrightarrow{H_{j}}v^{\prime}]=\left\{ \begin{array}{ll}1&,\text{ if }N_{H_{j}}(v)=\emptyset\text{ and }v^{\prime}=v\\ |N_{H_{j}}(v)|^{-1}&,\text{ if }v^{\prime}\in N_{H_{j}}(v)\\ 0&,\text{ otherwise}\end{array} \right.\] (1) Overall, we combine the two phases in \(M\) and introduce the following transition probabilities. * If \(|V_{c}|<n\): \[\Pr[(H,v,V_{c})\rightarrow(H^{\prime},v^{\prime},V^{\prime}_{c})]=\left\{ \begin{array}{ll}\Pr[H\xrightarrow{R}H^{\prime}]\cdot\Pr[v\xrightarrow{H^{ \prime}_{1}}v^{\prime}]&,\text{ if }v^{\prime}\in V^{\prime}_{c}\text{ and }V^{\prime}_{c}=V_{c}\\ \Pr[H\xrightarrow{R}H^{\prime}]\cdot\Pr[v\xrightarrow{H^{\prime}_{1}}v^{ \prime}]&,\text{ if }v^{\prime}\
eq v,v^{\prime}\
ot\in V^{\prime}_{c}\text{ and }V^{\prime}_{c}=V_{c}\cup\{v^{ \prime}\}\\ 0&,\text{ otherwise}\end{array} \right.\]
* If \(|V_{c}|=n\): \[\Pr[(H,v,V_{c})\rightarrow(H^{\prime},v^{\prime},V^{\prime}_{c})]=\left\{ \begin{array}{ll}1&,\text{ if }H=H^{\prime},v=v^{\prime},V_{c}=V^{\prime}_{c}\\ 0&,\text{ otherwise}\end{array} \right.\]  
For \(|V_{c}|<n\), notice that only two cases may have a non-zero probability with respect to the growth of \(V_{c}\). If the newly visited node \(v^{\prime}\) is already covered, then \(V^{\prime}_{c}\) must be identical to \(V_{c}\) since no new nodes are covered during this transition. Further, if a new node \(v^{\prime}\) is not yet covered, then \(V^{\prime}_{c}\) is updated to include it, as well as all the covered nodes in \(V_{c}\). For \(|V_{c}|=n\), the idea is that once such a state has been reached, and so all nodes are covered, then there is no need for further exploration. Therefore, such a state can be made to absorb. In this respect, let us denote the set of these states as \(\Gamma=\{(H,v,V_{c})\in M\ :\ |V_{c}|=n\}\). Definition 2: Let \(ECT(G,R)\) be the problem of determining the exact value of the cover time for an RWA on a graph \(G\) stochastically evolving under rule-set \(R\). Theorem 4.1: _Assume all probabilities of the form \(\Pr[H\xrightarrow{R}H^{\prime}]\) used in \(M\) are exact reals and known a priori. Then, for any underlying graph \(G\) and stochastic rule-set \(R\), it holds that \(ECT(G,R)\in EXPTIME\)._  
Proof: For each temporal graph instance, \(H_{i}\), in the worst case, there exist \(2^{m}\) possibilities, since each of the \(m\) possible edges is either alive or dead at a graph instance. For the whole history \(H\), the number of possibilities becomes \((2^{m})^{k}=2^{k\cdot m}\) by taking the product of \(k\) such terms. There are \(n\) possibilities for the walker's position \(v\). Finally, for each \(v\in V(G)\), we only allow states such that \(v\in V_{c}\). Therefore, since we fix \(v\), there are up to \(n-1\) nodes to be included or not in \(V_{c}\) leading to a total of \(\mathcal{O}(2^{n-1})\) possibilities for \(V_{c}\). Taking everything into account, \(M\) has a total of \(\mathcal{O}(2^{k\cdot m+n-1}n)\) states. Let \(H_{s,\Gamma}\) stand for the hitting time of \(\Gamma\) when starting from a state \(s\in M\). Assuming exact real arithmetic, we can compute all such hitting times by solving the following system (Theorem 1.3.5 [20]):  
\[\left\{ \begin{array}{ll}H_{s,\Gamma}=0&,\forall s\in\Gamma\\ H_{s,\Gamma}=1+\sum_{s^{\prime}\
ot\in\Gamma}\Pr[s\to s^{\prime}]\cdot H_{s^{ \prime},\Gamma}&,\forall s\
ot\in\Gamma\end{array} \right.\]  
Let \(C\) stand for the cover time of an RWA on \(G\) evolving under \(R\).