At the beginning we have a directed unweighted graph of $n \leq 10^3$ vertices, and $m \leq 10^5$ edges, with some vertex being a source, and we perform updates and queries on it. An update is adding some edge between two vertices $u$ and $v$. A query is asking, for some vertex $v$, what is $\mathrm{dist}(\mathrm{source},v)$ – the algorithm should also consider the possibility of being there no path at all, and return $-1$. The number $q$ of all operations (altogether, updates and queries) doesn't exceed $2\times 10^5$.

What I ask for is an algorithm that does the above with complexity significantly faster than the trivial $O((n+m)q)$.

It seems to me that in this problem we should either have a really quick time per operation (update and query), or there is some amortization to happen. If we stored distances from source to all other vertices explicitly, then answering a query would be a single lookup. When updating the graph, some of the distances may decrease, and others stay unchanged. Although one edge insertion can change almost all of the distances, every one of them is going to be some integer from $\{1,\dots,n\}$, so it follows that after any number of edge insertions changing one of the distances could happen at most $O(n^2)$ times, which is acceptable. For that to happen, we would need to somehow detect which distances from source to update, instead of just running BFS again, resulting in $O((n+m)q)$ complexity (the trivial approach mentioned earlier). Also note, that we don't need to answer queries instantly, so the version of this problem with edge deletions instead of edge insertions is exactly the same – all we have to do is "reverse time". In the case of edge deletions, I think it may be possible to somehow maintain the shortest paths DAG, and repair it when erasing an edge from it, but have no idea how.

  • $\begingroup$ What research have you done? There is lots written on data structures for dynamic graphs, and you can probably find papers on maintaining distances under insertions. Have you done some research on that? (Alternatively: perhaps you can somehow maintain a dynamic dag of SCCs, and use persistent union-find to keep track of the set of vertices in each SCC.) $\endgroup$ – D.W. Sep 3 '14 at 7:32
  • $\begingroup$ I saw a lot of papers on this, but most of them are very complicated. Also, the specifics of my problem is that there are many edges and queries, but not so many vertices, and this might play some important role. This task is from an old programming contest, for which there are no available solutions, but the desired solution is bound to be possible to code in an hour or two. I thought of union-find, but have no idea how to use it, since the graph is directed... $\endgroup$ – Cris Sep 3 '14 at 9:45

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.