Parameterized dynamic data structure for Split Completion
<|reference_start|>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 \cdot (k d \cdot \log n)^{\mathcal{O}(1)}$, and the amortized time complexity of an update is $5^k \cdot (k d \cdot \log n)^{\mathcal{O}(1)}$. The answer provided by the data structure is correct with probability $1-\mathcal{O}(n^{-d})$.<|reference_end|>
@article{majewski2024parameterized,
    title={Parameterized dynamic data structure for Split Completion},
    author={Konrad Majewski, Micha{l} Pilipczuk, Anna Zych-Pawlewicz},
    journal={arXiv preprint arXiv:2402.08816},
    year={2024},
    archivePrefix={arXiv},
    eprint={2402.08816},
    primaryClass={cs.DS}
}