Lovász [1]} initiated the study of edge splitting off by showing that any vertex \(s\)  with even degree in an undirected graph can be split off while maintaining the (Steiner) connectivity of the remaining vertices. (Later, more powerful splitting off theorems [2]} were obtained that preserve stronger properties and/or apply to directed graphs, but these come at the cost of slower algorithms. We do not consider these extensions in this paper.) The splitting off operation has emerged as an important inductive tool in the graph connectivity literature, leading to many algorithms with progressively faster running times being proposed for the edge splitting off problem [3]}, [4]}, [5]}, [6]}. Currently, the best running time is \(\tilde{O}(n^2)\) , which was obtained in the same paper of Benczúr and Karger that obtained the edge connectivity augmentation result [7]}. We improve this bound as well:

There is a randomized, Monte Carlo algorithm for the edge splitting off problem that runs in \(\tilde{O}(m) + \operatorname{polylog}(n)\cdot F(m, n)\)  time where \(F(m, n)\)  is the running time of any maximum flow algorithm on an undirected graph containing \(m\)  edges and \(n\)  vertices.
