Parameterized dynamic data structure for Split Completion

We design a randomized data structure that, for a fully dynamic graph G updated by edge insertions and deletions and integers $k, d$ fixed upon initialization, maintains the answer to the Split Completion problem: whether one can add k edges to G to obtain a split graph. The data structure can be initialized on an edgeless n-vertex graph in time n · (k d · log n)O(1), and the amortized time complexity of an update is 5ᵏ · (k d · log n)O(1). The answer provided by the data structure is correct with probability 1-O(n⁻ᵈ).