0
$\begingroup$

The wikipedia entry for disjoint set data structure includes the statement (in the "Applications" section)

Note that the implementation as disjoint-set forests does not allow the deletion of edges, even without path compression or the rank heuristic.

Is the article trying to say that a deletion is not possible with a similar time complexity as the optimized find/union (Inverse Ackermann function as the amortized running time)? Because a blanket statement that deletion is not possible seems like a stretch. There's nothing inherent in the data structure that prevents a deletion operation as long as it restructures the forest. It would be expensive when operating on a non-flattened set, but that isn't the same as not being possible.

Or am I overlooking something that (for instance) would make edge deletion an NP operation?

$\endgroup$

2 Answers 2

1
$\begingroup$

The tree structure of a Disjoint Set doesn't have enough data to perform a deletion.

There are many different graphs that produce the same Disjoint Set representation. E.g. if the graph contains 3 nodes a, b and c, and the Disjoint Set looks like a -> b -> c (a parent of b and b parent of c), then we could have a path graph with just two edges a - b and b - c, or a cycle graph with the edges a - b, b - c and c - a. And if you remove the edge a - b you either split the graph up into two components in case of the path graph, or keep it in one component in case of the cycle graph.

If you add more information to the Disjoint Set, then you could delete nodes. E.g. if you remember all added edges, then you can of course recompute the data structure after every deletion. But that of course ruins your runtime, in the case you delete a lot of edges. And it's definitely more than just a Disjoint Set.

There are of course more clever solutions. E.g. a fun one is described here: https://cp-algorithms.com/data_structures/deleting_in_log_n.html If you know all operations (additions, deletions, check-if-same-set queries) beforehand (so processing the operations offline), you can perform every add/delete operation in $O(\alpha(n) \log(n))$, by changing adding and deletion operations into just adding for a certain timespan operations, and then building a Segment tree over time. But again, it's now more than just a Disjoint Set, it's a more complicated data structure with more information.

$\endgroup$
1
  • $\begingroup$ So the statement which confuses me is actually saying that a deletion operation on the set isn't supported when it represents a graph. And (to paraphrase your answer) the tree structure of a Disjoint Set doesn't have enough data to perform a deletion while maintaining fidelity of edges because deletion might leave orphaned edges still connected to the ancestor. Thank you for the explanation! $\endgroup$ Commented Jan 26, 2022 at 17:43
1
$\begingroup$

That's a confusing statement indeed. I think the following is likely the intended interpretation:

Suppose we are building up an undirected graph by adding edges one at a time, and we want to keep track of the connected components of the graph. You can think of this as supporting one operation: AddEdge. Then a reasonable algorithm is to use union-find to keep track of the components, and this will be very efficient.

What if we want to delete edges too? You can think of this as supporting two operations: AddEdge and DeleteEdge. Then there is no longer a direct, efficient way to handle this (to track the component components) in this scenario. One crude approach might be to track connected components using union-find, update the union-find data structure whenever an edge is added; and if an edge is deleted, discard the entire union-find data structure and build it up from scratch again. Obviously, this would be slow and inefficient. It also requires keeping track of all of the edges that were previously added. Moreover, if you separately haven't kept a record of all edges that were previously added, then it is impossible, as the union-find data structure alone does not have enough information to determine what are the remaining edges.

So, "does not allow" could be interpreted as "does not allow, with similar efficiency, even with modifications to the algorithm", or it could be interpreted as "does not allow at any time efficiency, without modifications to the algorithm, because without modifications there is not enough information retained".

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.