I am given a (simple, undirected, connected) graph $G = (V, E)$ and a fixed spanning tree $T$ in this graph. Removing an edge $e\in E(T)$ from $T$ splits it into a spanning forest $F^e$ with two components $F_1^e$ and $F_2^e$. I am interested in the number $c(e)$ of edges in $G$ that connect $F^e$ i.e. with one vertex in $F_1^e$ and the other in $F_2^e$.

I would like to compute the number $c(e)$ for all $e$ in $T$ simultaneously. This can be done naively in $O(|V||E|)$. Is there a faster way to achieve this?

The graphs I am working with are small-world graphs. In particular the average distance between nodes in $G$ can be assumed to be small.


I have an idea that will efficiently get you "halfway there". Hopefully you or someone else can think of a way to extend this to get the "other half" efficiently.

For a given edge $uv$ in $T$, let me rename the two subtrees that deleting $uv$ would create as $F_u^{uv}$ (this is the subtree containing $u$) and $F_v^{uv}$ (the one containing $v$). Denote by $E_u^{uv}$ the subset of $E$ for which both vertices belong to the vertex set of $F_u^{uv}$ (i.e., the graph edges that are "completely within" the $u$-subtree of $F$), and similarly for $E_v^{uv}$.

For each edge $uv$ in $T$, if we can efficiently compute both $|E_u^{uv}|$ and $|E_v^{uv}|$ , then we can compute $c(uv)$ simply by subtracting these two counts from the total number $|E|$ of edges.

Half of the necessary counts can be computed in $O(|E|)$ time as follows:

  1. Root $T$ arbitrarily and consider all edges to be directed "down", away from the root.
  2. Preprocess $T$ for fast lowest common ancestor (LCA) queries.
  3. For each graph edge $uv$:
    • Increment a counter $\Delta_x$, where $x$ is the LCA of $u$ and $v$ in $T$.
  4. Compute $|E_v^{uv}|$ as $\Delta_v + \sum_{c:vc\in T}|E_c^{vc}|$ for each $T$-edge $uv$ using a single postorder DFS traversal (here $u$ is the unique parent of $v$ in $T$).

Since LCA can be computed in constant time after linear preprocessing, the above takes only $O(|E|)$ time and space to compute all $n-1$ of the $|E_v^{uv}|$ values. (I think of $|E_v^{uv}|$ as the number of edges "completely below" $uv$.) But it does not compute any of the $n-1$ $|E_u^{uv}|$ values -- the numbers of edges "completely above" $uv$ -- and I can't think of an efficient way to do so.

You can of course reroot $T$ at a different vertex and repeat the exercise: The directions of some edges will be reversed, and the $|E_v^{uv}|$ values computed for each of them can be used for the $|E_u^{uv}|$ values in the original rooting. You could repeat this until all edges have been covered in both directions -- if you were lucky enough to be given a $T$ that is a Hamiltonian path, just 2 rootings would suffice, but in general "covering" all edges this way could require as many as $n-1$ rootings (think of a star tree), which leaves us no better off than the original method.

Ideas anyone?


Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.