# Count bridging edges in a family of two component forests

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.

## 1 Answer

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?