5
$\begingroup$

Given a set $S$ of sets, what is the fastest algorithm to check if elements of $S$ form an anti-chain with respect to subset ordering? That is, how can I quickly decide if there exists two sets $A$ and $B$ in $S$ such that $A \subseteq B$?

$\endgroup$
  • 4
    $\begingroup$ This problem is SETH-hard at time $n^2$ (Williams 04). There is no $n^{2-\epsilon}$ algorithm for any $\epsilon > 0$ if the universe has size $\omega(\log n)$. Do you care about subpolynomial improvements over n^2 or is your universe very small? $\endgroup$ – Stefan Schneider Sep 5 '16 at 2:08
  • 1
    $\begingroup$ Thanks for the pointer. Exactly what I was looking for. The universe is not very small but I was hoping that some near linear time algorithm exists. So, I don't care about sub-polynomial improvements in this case. Also, if you write down your comment in an answer, I would be able to accept it :-) $\endgroup$ – Shahab Sep 5 '16 at 10:23
8
$\begingroup$

This problem is SETH-hard at time $n^2$ (Williams 04). There is is no $n^{2-\epsilon}$ algorithm for any $\epsilon > 0$ if the universe has size $\omega(\log n)$.

For small universe size ($c \log n$ for some $c$), there is an algorithm with time $n^{2-1/O(\log c)}$ (Abboud, Williams, Yu 15)

$\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.