Worst-Case Union-Find with Fast Deletions

In the classical union-find problem we maintain a partition of a universe of elements into disjoint sets subject to the operations union and find. Kaplan et al. [SODA 2002] studied an extension of this problem, where also deletions are allowed. They gave a data structure that for any fixed k supports find(x) and delete(x) in O(log_kn) worst-case time and union in O(k) worst-case time, where n is the number of elements in the set containing x. They asked if the delete time could be made faster than their find time. We answer this question affirmatively showing how to get the delete time down to O(log^∗n), while keeping the same time bounds for union and find.