Algorithms for subset testing and finding maximal sets

Abstract

In this paper we consider two related problems: subset testing and finding maximal sets. First, consider a sequence of n operations, where each operation either creates a set, inserts (deletes) an element into (from) a set, queries whether a particular element is in a set, queries whether or not one set is a subset of another, or queries whether or not the intersection of two sets is empty. We show that for any integer κ, one can implement subset and intersection testing in time O(n1-(1-κ )log n) and all of the other operations in time O(n1/κ log n). It requires O(n(κ)/κ) space. When κ = 2, this yields a worst case time complexity of O(n1/2 log n) per operation, and uses O(n3/2) space. Second, consider a set of sets, where the total size of the input is O(ri). We show that one can find those sets that are maximal (a set is maximal if it is not contained in any other set) in time O(mn), where m is the number of maximal sets.