<p>This problem is SETH-hard at time $n^2$ (<a href="http://www.sciencedirect.com/science/article/pii/S0304397505005438">Williams 04</a>). There is is no $n^{2-\epsilon}$ algorithm for any $\epsilon &gt; 0$ if the universe has size $\omega(\log n)$.</p>

<p>For small universe size ($c \log n$ for some $c$), there is an algorithm with time $n^{2-1/O(\log c)}$ (<a href="http://epubs.siam.org/doi/10.1137/1.9781611973730.17">Abboud, Williams, Yu 15</a>)</p>

CC BY-SA 3.0
2016-09-06T01:55:40.910Z
2016-09-06T01:55:40.910Z
Stefan Schneider
<p>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$?</p>

CC BY-SA 3.0
2016-09-05T02:08:10.340Z
This problem is SETH-hard at time $n^2$ ([Williams 04](http://www.sciencedirect.com/science/article/pii/S0304397505005438)). 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?
Stefan Schneider
CC BY-SA 3.0
2016-09-05T10:23:24.213Z
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 :-)
Shahab
<ds.algorithms><ds.data-structures>
Fast Algorithm to Check if a Set of Sets forms an Anti-chain
Shahab
# Fast Algorithm to Check if a Set of Sets forms an Anti-chain

(Asked by: username_0 on 2016-09-04)

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$?

**Tags:** ds.algorithms, ds.data-structures

> **Comments:**
> **username_1**: This problem is SETH-hard at time $n^2$ ([Williams 04](http://www.sciencedirect.com/science/article/pii/S0304397505005438)). 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?  
> **username_0**: 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 :-)  

---

## 1 answers

### Answer by username_1 on 2016-09-06. Score: 8 | Accepted answer

This problem is SETH-hard at time $n^2$ ([Williams 04](http://www.sciencedirect.com/science/article/pii/S0304397505005438)). 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](http://epubs.siam.org/doi/10.1137/1.9781611973730.17))


---

