11
$\begingroup$

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?

Hints.

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).

$\endgroup$
  • $\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 '14 at 15:15
  • $\begingroup$ @vzn The paper by Camil investigates edge removal right? $\endgroup$ – orezvani Sep 10 '14 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 '14 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 '14 at 12:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.