Find four sets where each element from those four appears in at least two of those four sets

Question

I have a list of sorted arrays ("sets") of integers $A_1..A_n$ where each element is unique w.r.t. the other elements in the same array:

• $A_i = \{x_{i,1}..x_{i,c_i}\}$
• $x_{i,p} < x_{i,p+1}$

$A_i$ has length $c_i$ and the average of $c_i \ll n$. For example in one of the runs, the average $c_i$ ranged from $10$ to $15$ and $n$ from $2000$ to $15000$.

I want to find all combinations of four different arrays $M=\{A_r,A_s,A_t,A_u\}$, where each element that appears in any of the $A$'s, appears in at least one of the other $A$'s:

$\forall A_i \in M: \forall x \in A_i: \exists A_{j \ne i} \in M: x \in A_j$

Assuming that only a small number of the combinations $\epsilon \ll n (\ll O(n^4))$ satisifies these requirements, is there a way to do this more efficiently than the obvious $O(n^4f(c))$? Here $f(c)$ is some reasonably small function in the average $c_i$.

It's probably viable for me if it can be done in $O(n^2c)$ but not if it's $O(n^3c)$.

If we consider the problem described so far to be the case with $|M|=4$, is there also an efficient algorithm for the case with $|M|=3$?

For the case with $|M|=2$, I can simply add each $A_i$ to a hash set after checking if another $A_j$ with the same values is already in the hash set, with expected time about $O(nc)$.

I'm also very interested in the cases where there's up to $y$ cases of $x_i$ that appear in only one of the sets of $M$, where $y = y'-|M|$ and $y'$ is $4$ or $5$

---

So where would I use such an algorithm? I'm writing a SAT solver. The idea of the solver is that it looks for an integer solution to an ILP problem (without inequality constraints). I have a rectangular matrix with very small integers (0,1,2 mod 3, without the n=2m constraint and the promise) and bring it into Smith normal form. To reduce the search search space, I look for a small set of rows with a small number of nonzero entries, but such rows could be hidden as linear combinations of the rows in the matrix. However since the matrix is in Smith normal form, a row with 4 nonzero entries can only be a linear combination of up to 4 rows, as any 5 rows have 5 pivots. Each row of the normal-form matrix becomes an $A_i$ in the described problem, with the pivot column removed.

The current implementation on github (first link above) only finds rows with 2 nonzero entries and it takes $O(n^2)$ in the worst case.

Answer 1

Assume set A has an element x. Then you need to add another set B which also has the same element x. Then if there is an item y element of A or B but not both, you need to add a set C contains y. And finally add a set D containing all elements that are elements of exactly one of A, B or C, plus possibly elements common to two of them.

I’d first count for each of the elements how many sets contain it; if x is contained only by one set A, then remove A from the problem. Sort the elements of each set by how many sets contain them. Sort the sets in lexicographic order according to the number of sets containing each element, except sets with fewer elements come later. (So if A contains x and y, both elements of two sets only, and B contains u and v both elements of two sets, and w element of 200 sets, then B comes before A, and both close to the start of the list).

You said that your sets tend to have 10 to 15 elements, then each element will tend to belong to not more than 10 or 15 sets. If you have much more than n different items in total, that number is actually smaller.

Now take the first set A in the list. Take its element x belonging to the smallest number of different sets, and pick each of these sets as the second set B in turn. Take the element y belonging to exactly one of A and B belonging to the smallest number of sets, and pick each of those sets as the third set C. Take the element z belonging to exactly one of A, B and C belonging to the smallest number of sets, and check all those sets in turn.

In cases where no element is required to be added (all elements belong to two of A, B and C for example), try all possible sets as the next set.

When all possibilities for B, C and D have been examined, remove A, adjusting all the counts. Assuming items don’t belong to more than k sets on average, this should take no more than n k^3 steps.

PS I assumed the number of different items is about the same as n. As long as the number of different items is at least n^(2/3) this will run in O(n^2). Well, roughly.