8
$\begingroup$

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?
$\endgroup$
  • 1
    $\begingroup$ This appears very closely related to boolean matrix multiplication. In particular, a lower bound for combinatorial algorithms for this problem would imply lower bounds for combinatorial algorithms for BMM. $\endgroup$ – Sasho Nikolov Sep 30 '16 at 22:36
  • 2
    $\begingroup$ The problem appears to be equivalent to the 2-dominating set problem for which $O(n^\omega)$ is the fastest known. This follows since a graph $G$ with adjacency matrix $M$ has a 2-dominating set if and only if there are at least two rows in the complement $\overline{M}$ of its adjacency matrix which are disjoint. See "On the complexity of fixed parameter clique and dominating set" by Eisenbrand and Grandoni for a paper stating that nothing faster than $O(n^\omega)$ is known for 2-dominating set. See also "On the possibility of faster SAT algorithms" by Patrascu and Williams. $\endgroup$ – JWM Oct 3 '16 at 13:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.