# Arranging sets in a hierarchy

Suppose you have sets $$S_1, \dots S_m$$ such that $$\sum_i |S_i| = n$$. The goal is to arrange all the sets into a (possible unconnected) DAG such that $$S_i$$ is a parent (or ancestor) of $$S_j$$ iff $$S_j \subseteq S_i$$. The domain of the elements over which $$S_i$$ are constructed can have size as large as $$O(n)$$ (so no word packing tricks or orthogonal vector style lower bounds).

Note that any set $$S_i$$ that is not a subset of some other set will be an isolated vertex in the graph. I wish to know the time complexity of solving this problem and possible lower bounds.

• What happens when there are 4 sets $A,B,C,D$ such that $A\subset B, A\subset C, B\subset D, C\subset D$? Mar 29, 2019 at 14:38
• @ChaoXu Excellent point! So the arrangement needs to be a DAG. I've edited the question to reflect that. Mar 29, 2019 at 15:32
• So you just want to compute the $m\times m$ Boolean matrix whose $(i,j)$ entry is $1$ iff $S_j\subseteq S_i$? Or do you want to represent the DAG in a different way? Mar 29, 2019 at 16:13
• @EmilJeřábek The matrix representation is fine. The trivial way would be to compute the matrix in $O(n \cdot m)$ time but I was hoping to get something smaller given that $m$ could be as large as $n$. Mar 29, 2019 at 16:33