A note on computing set overlap classes

Let V be a finite set of n elements and F={X1,X2,…,Xm} a family of m subsets of V. Two sets Xi and Xj of F overlap if Xi∩Xj≠∅, Xj∖Xi≠∅, and Xi∖Xj≠∅. Two sets X,Y∈F are in the same overlap class if there is a series X=X1,X2,…,Xk=Y of sets of F in which each XiXi+1 overlaps. In this note, we focus on efficiently identifying all overlap classes in time. We thus revisit the clever algorithm of Dahlhaus [E. Dahlhaus, Parallel algorithms for hierarchical clustering and applications to split decomposition and parity graph recognition, J. Algorithms 36 (2) (2000) 205–240] 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.