Stack Exchange network consists of 183 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.
Thanks for the insight! I guess this follows because $\tau_S$ is upper bounded by the time needed to see a set of $|S^c|+1$ vertices. Nice application of the theorem! :-)
Just one question. The statement '$H(u,S)$ in $G$ is the expected hitting time $H^*(u,s)$ in $G^*$ from $u$ to $s$' is only correct when you take into account the number of edges that u has to S, if I am correct? That means that $G^*$ will be a multigraph, and I am not sure if this changes anything in the correctness of the proof.
