The Subset Partial Order: Computing and Combinatorics
Amr Elmasry · 2010
Given a family ℱ of k sets with cardinalities s1, s2, …, sk and N = Σki = 1 si, we show that the size of the partial order graph induced by the subset relation (called the subset graph) is O(∑ii ≤ B 2si + N/log N · ∑si > B log(2Si/B)), where B = log (N/log2 N). This implies a simpler proof to the O(N2/log2 N) bound concluded in [2]. We also give an algorithm that computes the subset graph for any family of sets ℱ. Our algorithm requires O(nk2/log k) time and space on a pointer machine, where n is the number of domain elements. When ℱ is dense, i.e. N = Θ(nk), the algorithm requires O(N2/log2 N) time and space. We give a construction for a dense family whose subset graph is of size Θ(N2/log2 N), indicating the optimality of our algorithm for dense families. The subset graph can be dynamically maintained when ℱ undergoes set insertion and deletion in O(nk/log k) time per update (that is sub-linear in N for the case of dense families). If we assume words of b ≤ k bits, allow bits to be packed in words, and use bitwise operations, the above running time and space requirements can be reduced by a factor of blog (k/b + 1)/log k and b2 log (k/b + 1)/log k respectively.