A Note On Computing Set Overlap Classes

Original · EN

Let V be a finite set of n elements and F={X₁,X₂, >..., Xₘ} a family of m subsets of V. Two sets Xᵢ and Xⱼ of F overlap if Xᵢ ∩ Xⱼ ≠, Xⱼ Xᵢ ≠, and Xᵢ Xⱼ ≠. Two sets X,Y∈ F are in the same overlap class if there is a series X=X₁,X₂,..., Xₖ=Y of sets of F in which each XᵢXᵢ₊₁ overlaps. In this note, we focus on efficiently identifying all overlap classes in O(n+∑ᵢ₌₁ᵐ |Xᵢ|) time. We thus revisit the clever algorithm of Dahlhaus of which we give a clear presentation and that we simplify to make it practical and implementable in its real worst case complexity. An useful variant of Dahlhaus's approach is also explained.