0
$\begingroup$

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.

Improve this question
$\endgroup$
4
  • 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, 2019 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, 2019 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, 2019 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, 2019 at 16:33

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.