7
$\begingroup$

Consider the following empty intersection problem:

INPUT: a ground set $[n]:=\{1, \ldots, n\}$; a set family $S_1, \ldots, S_m$ s.t. $S_i\subseteq [n]$ for every $1\leq i\leq m$
TASK: on query $X\subseteq [n]$ decide whether there exists $1\leq i\leq m$ s.t. $S_i\cap X = \emptyset$.
TASKbis: on batch queries $X_1, \ldots, X_k\subseteq [n]$ decide whether $S_i\cap X_j=\emptyset$ for each $i,j$.

I'm in deep search for references about this problem, both TASK as well as the batched version TASKbis: fast algorithms (sequential, parallel, randomized, any other model is appreciated), also complexity lower bounds or other characterizations...

Observe that we can impose special values of $m$, for example consider $m=n^2$, or similar ...

Improve this question
$\endgroup$
10
  • $\begingroup$ Is the problem typically dominated by n or by m? I guess I would have thought n all the way until you mentioned m = n^2 at the end, so maybe others have a similar question... $\endgroup$
    – J Trana
    Dec 24, 2013 at 8:00
  • $\begingroup$ In the setting I have in mind, it is dominated by $m$, but by "small" polynomial factor, i.e. $m=O(n^2), m=O(n^3)$. $\endgroup$
    – XORwell
    Dec 24, 2013 at 10:15
  • $\begingroup$ Ok, good to know. And can you bound n any further? While this may well be the theoretical CS site, there's still a huge difference between say n=32 and n=1024. $\endgroup$
    – J Trana
    Dec 24, 2013 at 19:31
  • $\begingroup$ Hi Trana, no, in theory I would not bound $n$ any further, I would like to focus on asymptotic bounds in this setting. $\endgroup$
    – XORwell
    Dec 25, 2013 at 15:26
  • 1
    $\begingroup$ The simplest case where $m=1$ is Set Disjointness, for which there are $\Omega(n)$ communication lower bounds (even in the randomized or approximate settings). $\endgroup$
    – András Salamon
    Dec 25, 2013 at 23:23

2 Answers 2

Reset to default
6
$\begingroup$

As you might have realized by now, this problem is closely related to Matrix Multiplication.

Particularly: Task B asks to preprocess an m by n matrix S, such that given as a query a n by matrix X, we need to compute the m by m boolean product SX. For particularly structured matrices S, this can be solved by something like FFT. But I suspect that for a non-structured S (say random S) the best you could do is used fast matrix multiplication.

If the matrices S and X are sparse (i.e. the input sets are of cardinality << n) then there are some algorithms for sparse matrix multiplication that can give some good results.

About the first task, it's of course even harder-looking, and I suspect that, unless the input S is of one of those special structures, the best approach is the naive one that takes O(n) time per query.

Improve this answer
$\endgroup$
5
  • $\begingroup$ Hi mobius-dumpling, thank you for answer, yes the problem is reducible to instances of matrix multiplication. $\endgroup$
    – XORwell
    Dec 25, 2013 at 15:38
  • $\begingroup$ Nice answer! I noticed some typos. "n by matrix X": do you mean "n by k matrix X"? "m by m boolean product SX": do you mean "m by k boolean product SX"? $\endgroup$
    – D.W.
    Dec 26, 2013 at 7:10
  • $\begingroup$ I'm not sure the ‘naive’ approach that solves the basic TASK in $O(n)$ is obvious. One way is to pre-compute a BDD for the function $f(x_1,\ldots,x_n)=\lor_{i=1}^m(\land_{j\in S_i}x_j)$ and then evaluate $f(\lnot X)$. (By $\lnot X$ I mean $x_k=1$ iff $k\notin X$.) $\endgroup$
    – Radu GRIGore
    Dec 29, 2013 at 18:12
  • $\begingroup$ By computing a BDD or ZDD for family of sets $\{S_i\}_i$ we still have $O(mn)$ total time on query $X$, by considering worst-case ZDD-compression, haven't we ? $\endgroup$
    – XORwell
    Dec 30, 2013 at 16:46
  • $\begingroup$ @XORwell: Building the BDD (not ZDD!) may even take exponential time (and space). But, once preprocessing is done, answering one query $X$ amounts to evaluating a BDD, which is $O(n)$, not $O(mn)$. $\endgroup$
    – Radu GRIGore
    Dec 31, 2013 at 9:10
4
$\begingroup$

Here is how to solve the basic task in $O(n)$, at the expense of possibly lots of preprocessing. (This expands a comment I made.)

Example. Suppose that $n$ is 3, and the given sets are {1,2}, {2,3}. Represent the boolean function $f(x_1,x_2,x_3)=(x_1\land x_2)\lor(x_2\land x_3)$ as a BDD: $$f(x_1,x_2,x_3)=x_1?(x_2?1:0):(x_2?(x_3?1:0):0)$$ (Here $x?a:b$ means 'if $x$ then $a$ else $b$'.) Clearly, evaluating $f$ written in this form takes time linear in $n$, which is possibly much smaller than the size of the input. The problem, of course, is that going from DNF to BDD may take an exponential amount of time (and space). But this is just preprocessing.

Suppose the query is the set {1}. We evaluate $f(0,1,1)$ to get 1, so we conclude that one of the given sets is disjoint from the query.

Suppose the query is the set {2}. We evaluate $f(1,0,1)$ to get 0, so we conclude that none of the given sets is disjoint from the query.

The general case. Given sets $S_1,\ldots,S_m\subseteq[n]$, represent the function $$f(x_1,\ldots,x_n)=\bigvee_{i=1}^m\bigwedge_{j\in S_i}x_j$$ as a (RO)BDD. To answer a query $X$ evaluate $f(x_1,\ldots,x_n)$ with $x_j=[j\notin X]$ for $1\le j\le n$.

Comments. One way to view this construction is as a systematic way to precompute all answers. ‘Precompute all answers’ sounds dissatisfying, but I think the keyword should be ‘systematic’: it's not a priori obvious how to do it for this problem, given the comments on the question.

Another thing to note is that there are many negations going on here, which some people say are obvious, but they tend to make me dizzy. Probably the only reason I saw this construction quickly is that minutes before reading the question I was looking at the Monotone Duality problem, which is closely related to the question. Monotone Duality comes in many guises. One of them is Hitting-Sets: Given a family of sets, compute the family of all the hitting sets. This is clearly related to the question posed here, in which we are asked whether a given set is not a hitting set. (It's not the same though.) Another guise is Monotone-DNF-Dual: Given a monotone $f$ in DNF, find a $g$ in DNF such that $\lnot f(x_1,\ldots,x_m)=g(\lnot x_1,\ldots,\lnot x_m)$. I thought of the construction above because I knew that this is an equivalent formulation. So, perhaps a reference to a survey of the Monotone Duality problem would serve as a suitable reference:

What does this construction say about lower bounds? Not much. But it does say that if you find a solution that answers a query in $O(h(m,n))$ time after $O(g(m,n))$ time preprocessing, then there exists a representation for monotone boolean functions that takes $O(g(m,n))$ space and allows evaluation in $O(h(m,n))$ time. For example, BDDs have exponential $g$ and $h(m,n)=n$. The reference for ‘exponential $g$’ is

PS: I would be grateful for any comments on how to improve this answer.

Improve this answer
$\endgroup$

Your Answer

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

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