A Note On Computing Set Overlap Classes

Abstract

Let $\mathcal{V}$ be a finite set of $n$ elements and $\mathcal{F}=\{X_1,X_2,>...,X_m\}$ a family of $m$ subsets of $\mathcal{V}.$ Two sets $X_i$ and $X_j$ of $\mathcal{F}$ overlap if $X_i\cap X_j\ne \varnothing ,$ $X_j\setminus X_i\ne \varnothing ,$ and $X_i\setminus X_j\ne \varnothing .$ Two sets $X,Y\in \mathcal{F}$ are in the same overlap class if there is a series $X=X_1,X_2,...,X_k=Y$ of sets of $\mathcal{F}$ in which each $X_i{X}_{i+1}$ overlaps. In this note, we focus on efficiently identifying all overlap classes in $O(n+{\sum }_{i=1}^m|X_i|)$ 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.