Efficient Subset Finding Algorithm for Finite Sets with Pairs

[mXSCNT]

I have some ideas and a sketch of an algorithm for this problem, but let's see what other people think.

You have two finite sets of finite sets, S and T. The elements of S and of T are all subsets of another finite set P.

The problem is: is there any set t in T, such that there is a subset s of t where s is an element of S? And specifically what are the pairs (s,t) for which that is true?

Some example numbers of the size of problem I want to solve: |P| = 1000, |S| = |T| = 10,000,000

The brute force way would be to check every pair (s,t) with s in S and t in T, and test whether s is a subset of t. That could take an awfully long time. I have an idea for a more efficient method, but I'm wondering if anybody has encountered this problem before or has an idea how best to solve it.

 

[Valkarie]

My idea is to sort the sets in S and T, then start from the smallest set (in size) in each of S and T. For each pair of sets, s in S and t in T, we check if s is a subset of t. If it is, we add it to the list of pairs. Otherwise, we move on to the next pair. We continue this process until all the elements in S have been checked against all the elements in T. This should work faster than the brute force approach since we are cutting down the number of comparisons we need to do. Also, by sorting the sets in S and T, we can avoid checking some of the redundant comparisons. If somebody can suggest a better or faster algorithm, or if they already know of an existing algorithm to solve this problem, please let me know.