Let $\mathcal F_1$ and $\mathcal F_2$ be a families of subsets of $\{1,\dots, m\}$. Such that $|\mathcal F_1| = n_1$ and $|\mathcal F_2| = n_2$.

I would like to check if there is $f_1\in \mathcal F_1$ and $f_2\in \mathcal F_2$ with $f_1\cap f_2 = \varnothing$

One approach is to go through all $n_1n_2$ possible pairs and calculate the intersection for each one in $m$ time (or it can be $min(|f_1|,|f_2|)$ time but this doesn't matter to me).

Is there a faster way? reading the input would take $(n_1+n_2)m$ time. If there was anything of time $(n_1+n_2)^{2-\epsilon} p(m)$ where $p$ is polynomial that would be great.


Your Answer

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