1
$\begingroup$

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?

$\endgroup$
8
  • $\begingroup$ What is the most efficient algorithm you've been able to come up with yourself? This will help us avoid repeating things you are already aware of. I encourage you to edit the question to show that. $\endgroup$
    – D.W.
    Jun 8, 2023 at 21:48
  • $\begingroup$ @D.W.Besides the obvious "coun't all the pairs,sort by counts" I don't really have a good idea. $\endgroup$
    – fuz
    Jun 8, 2023 at 21:57
  • $\begingroup$ What are you looking for? Do you want to minimize the theoretical worst-case running time? How do you want to measure the running time? What parameters should we use? The number $n$ of sets and the size $k$ of the largest set? The number $n$ of sets and the total size $s$ of all of the sets? Something else? If you want a practical algorithm, what can you tell us about the typical value of $n$, typical size of the sets, and whether all sets have a similar size or what the distribution of sizes is? $\endgroup$
    – D.W.
    Jun 9, 2023 at 8:05
  • $\begingroup$ @D.W. I'm okay with an approximative algorithm. In my use case, $n$ is up to about $10^7$ and $k$ maybe of order $10^3$. Most sets are however much smaller, holding around $60$ elements. There are also a lot of sets holding a very small number of elements. The distribution of set sizes is similar to an exponential distribution. $\endgroup$
    – fuz
    Jun 9, 2023 at 8:12
  • 1
    $\begingroup$ @Dmitry The set datastructure already exists and a bunch of metrics can be precomputed (such as how often each integer appears), so I was hoping that perhaps this can be narrowed down to a small candidate set quickly and looking at the whole input can be avoided. The motivation is from the context of CDCL SAT solvers: I would like to find literals that often appear together in clauses and replace them with new variables. $\endgroup$
    – fuz
    Jun 11, 2023 at 19:43

2 Answers 2

2
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ This sounds like a reasonable approach, though the $O(m^2 l)$ time is where I believe it is likely to take too long. In my case, $m$ is around $10^6$, so anything that runs in $O(m^2)$ time is likely to be prohibitively (but so is anything that needs to run in $O(n^2)$ time for $n$ sets). $\endgroup$
    – fuz
    Jun 11, 2023 at 10:35
  • $\begingroup$ @FUZxxl: what do you know about $l$ ? $\endgroup$
    – user16034
    Jun 11, 2023 at 15:43
  • $\begingroup$ @FUZxxl: as another heuristic optimization, one can process the integers by decreasing list length, hoping that long lists will result in more pairs. But in this case it is not possible to predict the complexity. $\endgroup$
    – user16034
    Jun 11, 2023 at 15:47
  • $\begingroup$ I don't know the value of $l$ for sure. Some elements are contained in a large share of sets, others in very few. The optimisation sounds interesting, I'll try and fiddle around with it. $\endgroup$
    – fuz
    Jun 11, 2023 at 17:23
1
$\begingroup$

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$:

      • Set $h[x,y] := h[x,y] + 1$.
  • 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$:

        • Set $h[x,y] := h[x,y] + 1$.
  • 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):

  1. 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$.

  2. 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$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.