2
$\begingroup$

We are given a tree with $n$ vertices and some of the vertices act as a "hotspot".

We have to answer multiple queries of type $(a,b,c)$, which means we have to find the distance to the nearest hotspot from $c$ such that we do not travel through the edge between nodes $a$ and $b$.

I have tried many data structures like using lowest common ancestor and algorithms like mo's algorithm on a tree, I have also tried to process queries which are closer to root first, but none of these have given me the desired complexity for each query which is anywhere between $O(1)$ to $O(\log n)$.

Is there any better algorithm or perhaps some clever precomputation(in less time than $O(n\log n)$ that can be used to solve this problem?

$\endgroup$
  • $\begingroup$ can you aid your question with a graph diagram, showing the query on a example graph? $\endgroup$ – Rahul roy May 12 at 7:30
  • $\begingroup$ If we process the queries for each (a, b) in order, can we have an O(log n) update procedure to add that edge back in and remove the next, updating all relevant distances? $\endgroup$ – גלעד ברקן May 12 at 12:49
1
$\begingroup$

You can use the top-tree data structure. It maintains a forest $F$ on $n$ nodes and supports (among others) each of the following operations in $O(\log n)$ time per operation:

  • Given an unmarked vertex $v$ mark $v$.
  • Given a marked vertex $v$ unmark $v$.
  • Given two vertices $u,v$ that belong to two different trees in $F$, add the edge $(u,v)$ to $F$ (thus merging two trees into one).
  • Given an edge $(u,v)$ of a tree in $F$, delete $(u,v)$ from $F$ (thus splitting the three into two).
  • Given a vertex $v$, report the distance to the marked vertex that belongs to the tree of $v$ and is closest to $v$.

This allows you to preprocess your tree in time $O(n \log n)$: build the forest $F$ on $n$ nodes by adding the edges of the tree one by one (so that, at the end, $F$ contains the input tree), then mark each hotspot.

To answer a query $(a,b,c)$ in time $O(\log n)$ proceed as follows:

  • Delete $(a,b)$ from $F$ in time $O(\log n)$.
  • Find the distance $d$ to the marked vertex that is closest to $c$. This takes $O(\log n)$ time and is exactly the answer to the query.
  • Re-add $(a,b)$ to $F$ in time $O(\log n)$.
  • Return $d$.
| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Can you elaborate more on how to process the query? $\endgroup$ – user120976 May 11 at 20:28
  • 1
    $\begingroup$ I expanded that part of the answer. Is it clearer now? $\endgroup$ – Steven May 11 at 20:34
  • $\begingroup$ I don't understand how to find the closest marks vertex to c in log(n) as each vertex in the top-tree represents and edge so there is no notion of an edge being marked and unmarked $\endgroup$ – user120976 May 11 at 20:38
  • $\begingroup$ Each vertex of the original tree is a vertex in the top tree. Each edge of the original tree is an edge in the top tree. In other words, the forest $F$ maintained by the top-tree contains only one tree which is exactly your input tree. $\endgroup$ – Steven May 11 at 20:54
  • $\begingroup$ I tried reading some papers on top-tree and couldn't understand some terminologies such as ∂T, and external boundary vertices. Is there in a resource that explains this complex data-structure such that a novice like me can understand? $\endgroup$ – user120976 May 11 at 21:41
1
$\begingroup$

Merge all hotspots into a single node $h$ (Instead of a tree - the input is now an undirected graph). The problem can now be represented as follows:

Given an undirected graph $G$ and a node $h$ (the merged hotspot), we want to answer queries $Q(c, e)$:

$Q(c, e)$: Given node $c\in G$ and edge $e\in G$, return $\mathrm{distance}(h, c)$ in $G\setminus \{e\}$.

This is a dynamic problem, or more specifically: an edge-decremental single-source shortest-path distance problem (also called single-source edge-removal exact distance oracle).

In [1], the preprocessing time is $O(mn^{1.5} + n^{2.5} \log n)$ and the query time is $O(1)$. This is an All-Pairs Shortest Paths algorithm, while you require only a single-source algorithm.

[2] improves the results to $O(\sigma^{0.5}\cdot n^{1.5})$ preprocessing time and $O(1)$ query time. $\sigma$ is the number of sources (in your case: $\sigma=1$ - the merged hotspot).

Following [2], you can get an $O(n^{1.5})$ preprocessing time and $O(1)$ query time using $O(n^{1.5})$ memory.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ I don't understand how can one consider all hotspots as a single node $\endgroup$ – user120976 May 12 at 14:49
  • $\begingroup$ Since you don't care which hotspot you reach, and since once a hotspot is reached - you're done, nothing prevents you from regarding them all as the same node. This is an equivalent graph you need either to construct or process the tree as it was such. $\endgroup$ – Lior Kogan May 12 at 15:11
  • $\begingroup$ Also note that the equivalent problem is reversed: reach c from the 'united hotspot' instead of reaching any hotspot from c. $\endgroup$ – Lior Kogan May 12 at 15:11
  • $\begingroup$ OP wrote "distance to the nearest hotspot." $\endgroup$ – גלעד ברקן May 12 at 16:00
  • $\begingroup$ @גלעדברקן: Yes.... that's in line with my answer. Why do you think it is not so? (re my note above: we don't care which hotspot to reach as long as it is the nearest hotspot). $\endgroup$ – Lior Kogan May 12 at 16:12

Your Answer

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