Given a collection of sets $C=\{S_1, S_2, \ldots, S_n\}$ with each $S\in C$ holding some integers, I would like to find a pair $\{x,y\}, x\ne y$ such that $\{x,y\}\subset S$ for the highest number of $S\in C$ among all such pairs.
Is there an efficient algorithm to find such a pair?
Not an optimal answer, just a possible solution, close to brute-force.
list all integers from all $S_k$ and store them in a map; to each integer, associate the list of sets that contain it; sort these lists by set index. For $m$ distinct integers and an average list length $l$, this process will take like $O(m \,l\log(l))$ time and $O(m\,l)$ space.
try all integers in turn; for every integer, try all larger integers (to form all possible pairs) and take the intersection of the two lists of sets by a merge-like process; keep the longest intersection. This takes $O(m^2\,l)$ operations.
As a heuristic optimization, you can skip trying the elements with a list of sets smaller than the current best length.
Update: trying the elements by decreasing list length might reinforce the above heuristic.
Here is a plausible heuristic. It has no guarantees of approximation factor, but might be useful in practice given the problem sizes you mentioned. Pick a threshold $\tau$, say $\tau=100$, chosen to balance running time vs quality of approximation. Execute the following algorithm:
Initialize $h$ to an empty hashmap (with a default that if you look up a nonexistent key, the lookup returns 0).
For each set $S \in C$ such that $|S| \le \tau$:
For each pair $x,y \in S$ with $x<y$:
Optionally, delete all entries $x,y$ such that $h[x,y] \le \kappa$, for some constant $\kappa$ chosen to balance between running time vs approximately quality.
For each $S \in C$ such that $|S| > \tau$: (a)
For each $x \in S$:
Find all $y$ such that $y \in S$ and $h[x,y]>0$. (b)
For each such $y$, such that $y>x$:
Output the pair $x,y$ such that $h[x,y]$ is maximized.
To improve the running time at the cost of reduced quality of approximation, you might be able to skip the loop marked (a).
There are many ways to implement the line marked (b):
You can iterate through all elements of $S$, and look them up in $h$. The running time will be linear in the size of $S$.
If you use an appropriate datastructure, you can implement the line (b) to run in time linear in the size of $S$ or $\{y \mid h[x,y]>0\}$, whichever is smaller. In particular, for each $x$, you can keep track of $\{y \mid h[x,y]>0\}$, sorted in order of increasing $y$. Then, you can merge those two sets using a standard merge-join, advancing the pointer where needed using binary search. This might be faster, especially if you delete entries of $h$ based on $\kappa$.
