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

<p>Note that any set <span class="math-container">$S_i$</span> 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.</p>

CC BY-SA 4.0
2019-03-29T14:38:11.283Z
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$?
Chao Xu
CC BY-SA 4.0
2019-03-29T15:32:47.780Z
@ChaoXu Excellent point! So the arrangement needs to be a DAG. I've edited the question to reflect that.
karmanaut
CC BY-SA 4.0
2019-03-29T16:13:48.917Z
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?
Emil Jeřábek
CC BY-SA 4.0
2019-03-29T16:33:01.540Z
@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$.
karmanaut
<ds.data-structures><time-complexity><lower-bounds>
Arranging sets in a hierarchy
karmanaut
# Arranging sets in a hierarchy

(Asked by: username_0 on 2019-03-29)

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.

**Tags:** ds.data-structures, time-complexity, lower-bounds
> **Comments:**
> **username_1**: 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$?  
> **username_0**: @ChaoXu Excellent point! So the arrangement needs to be a DAG. I've edited the question to reflect that.  
> **username_2**: 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?  
> **username_0**: @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$.  

---

## 0 answers

