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.

  • 2
    $\begingroup$ 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$? $\endgroup$ – Chao Xu Mar 29 at 14:38
  • $\begingroup$ @ChaoXu Excellent point! So the arrangement needs to be a DAG. I've edited the question to reflect that. $\endgroup$ – karmanaut Mar 29 at 15:32
  • $\begingroup$ 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? $\endgroup$ – Emil Jeřábek Mar 29 at 16:13
  • $\begingroup$ @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$. $\endgroup$ – karmanaut Mar 29 at 16:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.