Given an undirected unweighted graph $G=(V,E)$ and a node $s \in V$, we are looking for a vector $\operatorname{diff}[]$, such that,

$$\operatorname{diff}[v] = \sum_{u \in V \setminus \{v\}}{(d^{G \setminus \{v\}}_{su}-d^G_{su})}$$

In other words, we are looking for the difference in distances from $s$ to every other nodes after removal of each node $v$.

Now the question: is there an algorithm with time complexity $O(n+m)$ that can calculate the vector $\operatorname{diff}$ for a given graph $G$ and node $s$? If yes, what is the algorithm (or the idea behind that algorithm)?

For a specific node $v$, we can run BFS on $G$ and $G \setminus \{v\}$ and find the $\operatorname{diff}[v]$ in $O(n+m)$, but here we want $\operatorname{diff}$ for all of the nodes.

I know that we can determine, whether $\operatorname{diff}[v] >0$ for every node $v$ (using shortest path tree of $s$), in $O(n+m)$, but is there an algorithm to find the exact value of $\operatorname{diff}$ in $O(n+m)$ time complexity?


There are some properties in the shortest path tree that may help:

  1. If we construct the SPT, and then add the other edges of the graph that are not in the SPT, there will be edges from one level to the next level, or edges among nodes within the same level.

  2. When we remove a node $v$, only the distance between $s$ and the descendants of $v$ can be changed.

  3. For a node $v$, if all the descendants have another neightbour in $G$ that is on the same level as $v$ in the SPT, then $diff[v]=0$.

  4. For every descendant of $v$, if we keep track of the incoming edges whose other endpoint is in another subtree (subtree of siblings of $v$), we can easily update the distances for its children (Suppose that child is $v'$, the change in $diff[v]$ for such $v'$ will be $\min{(diff[v']+1,(d^{new}_{sv'}-d_{sv'})\cdot(\# \text{children whose endpoint is in the subtree of }v)+(\text{new distance of nodes whose endpoint is outside subtree of v}))}$).

We can assume that the graph is 2-vertex-connected, which means that it will not be disconnected by removing one node (otherwise we can find all the vertex cuts of size of using DFS and check each connected component separately).

  • $\begingroup$ suggest looking into "online algorithms" or "incremental/ decremental". seems like an online version of APSP eg online version of APSP tcs.se $\endgroup$
    – vzn
    Sep 9, 2014 at 15:15
  • $\begingroup$ @vzn The paper by Camil investigates edge removal right? $\endgroup$
    – orezvani
    Sep 10, 2014 at 0:53
  • 1
    $\begingroup$ there are at least 3 papers by Camil on that page, & online paper links are not given so far. the papers generally look at adding/ removing vertices/ edges. $\endgroup$
    – vzn
    Sep 10, 2014 at 2:47
  • $\begingroup$ @FrankW If that distance goes through a child, then it will be the minimum is the first term $diff[v']+1$. $\endgroup$
    – orezvani
    Sep 11, 2014 at 12:22


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.