Count bridging edges in a family of two component forests

Question

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.

Answer 1

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?