I am interested in the best currently known algorithm (in fact, any relevant reference) for the following problem:
Given a family of subsets $S_1,S_2,\ldots S_N\subseteq \{1,2,\ldots N\}$, determine if there is a pair of disjoint subsets $S_i\cap S_j=\emptyset$.
This is the $k=2$ case of set packing problem; by taking complements, we obtain the $k=2$ set cover problem. An obvious generalization considers $M$ subsets.
There is a straightforward reduction to matrix multiplication: if $B$ is the incidence matrix of the family $\{S_1,\ldots S_N\}$, then we can check if $BB^T$ has a zero element in $O(N^{2.373})$ time.
Curiously enough, the only discussion of this problem in literature I was able to come by was an elementary textbook by Kleinberg and Tardos where it was given as an example of $O(N^3)$ complexity, followed by "For this problem, there are algorithms that improve on $O(N^3)$ running time, but they are quite complicated. Furthermore, it is not clear whether the improved algorithms for this problem are practical on inputs of reasonable size". The wording, however, suggests that matrix multiplication was assumed.
- Is there a $O(N^2\mathrm{polylog}(N))$ algorithm for this problem? Conversely, would such an algorithm necessarily imply an improvement in matrix multiplication?
- Assume we restrict the algorithm to decision trees in some way in order to exclude integer arithmetic and thus fast matrix multiplication. Are there nontrivial lower bounds for this case?
- A weakened version is equivalent to testing whether a given graph has diameter at least $3$. Is this problem known to be easier than all-pairs-shortest-paths?
