As edges are deleted from \(G\) , the recursive structure of the \(c\) -certificate \(H\)  changes. Indeed, the deletion of an edge may cause the following changes in one of the recursive layers of \(H\) : (1) introduce a cut of size less than \(\delta \)  surrounding a \(c\) -edge-connected component or (2) break a \(c\) -edge-connected component in two. In the first case, the edges of the cut have to be moved to \(D\) , and deleted from the current and later layers of \(H\) , causing further cascading.
When a \(c\) -edge-connected component (in a recursive layer) of \(H\)  breaks in two, we need to determine whether either of the new components has less than \(\delta \)  outgoing edges in \(G\) . If we use the standard technique of iterating over all the edges incident to nodes of the smaller component, this again incurs an \(O(\log (n^2/m))\)  cost per edge which is insufficient.
However, as we only care about components with at most \(\delta \)  outgoing edges, it turns out that we can do better.
We define the boundary of a component \(C\)  of some graph \(H\subset G\)  to be the set of edges of \(G\)  with one endpoint in \(C\) , and another in \(V\setminus C\) .
To overcome the \(O(\log {(n^2/m)})\)  cost per edge, we prove that we can maintain boundaries of size at most \(\delta \)  under splits using a Monte Carlo randomized algorithm in \({O(m+n\delta \operatorname{polylog}{n})}\)  total time. We realize this result by deploying the XOR-trick [1]}, [2]}, [3]} in a somehow unusual manner. In particular, we randomly partition the set of edges of \(G\)  and use the XOR-trick to detect the parts that are relevant for scanning, as opposed to standard applications of the XOR-trick, which are used to detect a single replacement edge over a polylogarithmic number of independent samples which unavoidably introduces a polylogarithmic dependence in the cost per edge. Since we are not interested in discovering a single edge incident to some set, we only need to apply the XOR-trick once, which allows us to keep the running time linear in \(m\) .
