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$
2
  • 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$ Commented Sep 5, 2016 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
    Commented Sep 5, 2016 at 10:23

1 Answer 1

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 and acknowledge you have read our privacy policy.

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