How to reconstruct a fundamental cycle basis after removing an edge from its spanning tree in the most efficient way?

Question

I would like to remove an edge $e$ from a spanning tree $S$ of a simple, connected graph $G$ and reconstruct its fundamental cycle basis (FCB) after linking a suitable non-tree edge to $S-e$. Could you please help me what is the most efficient way to perform it? What cost would be necessary to obtain the reconstructed FCB?

Answer 1

There will be another edge $e'$ which you are adding to $S-e$ to make $S-e+e'$ a spanning tree again.

For each edge $f$ outside the tree, there was a cycle $C(f)$ in the fundamental cycle basis. These change as follows:

• $C(e')$ is no longer an element of the cycle basis, since $e'$ is part of the new tree.
• If $C(f)$ did not use the edge $e$, then it remains as it was.
• If $C(f)$ did use the edge $e$, replace it by $C(f) + C(e')$ (after canceling double edges). The effect of this is to replace $e$ by a path in the tree $S-e+e'$ that goes through $e'$.