Efficiently representing a set of sets (The question is an extension of this unanswered question on stackoverflow)

If we have a set of strings, we can efficiently represent them with tries. Common branches can also be merged, resulting in a DAG instead of a tree that is even more compact.

However, if we have a set of sets (i.e. the order does not matter), there are a lot of possible tries that represent the same set of elements.
An example can be found in the stackoverflow question I linked above.

Edit: For example, assume that we are given the following sets of integers.

{1,2,3,4,5}
{1,2,6,7}
{1,2,4,7}
{1,3,5,7}


Two possible representations are shown below (trie on the left, DAG on the right)



My questions are:


  
  How hard is the problem of finding an optimal (i.e minimal) such trie? 
  Are there any fast algorithms for solving this problem?
  If not, are there any fast algorithms that find "good" tries?
  What about the DAG case?
  


In the scenario I have in mind there is an additional constraint that no set is a subset of another set.

Any link/paper that is even slightly relevant to any of the questions is helpful.
I suggest you start by looking at BDDs and ZDDs.

Your problem is similar to the problem of finding an optimal BDD.

I'll explain.  Suppose we have sets $S_1,\dots,S_k$ over a universe $U$ containing $n$ items (so $S_i \subseteq U$).  A BDD is a finite-state automaton (a DAG) for recognizing the language of all of the allowed sets, where each set is presented to the finite-state automaton as the $n$-bit string that is the characteristic function of that set.  In other words, given a total order on $U$, each set $S \subseteq U$ corresponds to a binary string $[S] \in \{0,1\}^n$: $[S]_i=1$ if $S$ includes the $i$ element of $U$, otherwise not.  (This order is known in the BDD literature as a "variable ordering".)  Then define the language $L$ by $L=\{[S_1],[S_2],\dots,[S_k]\}$.  A BDD is a finite-state automaton that recognizes the language $L$.

Notice that you have the freedom of what "variable ordering" to choose.  The choice of the variable ordering determines how each set is represented as a binary function, which can affect the size of the BDD.  It is well-known that the problem of choosing the optimal variable ordering (the one that leads to the smallest BDD) is NP-hard.  Nonetheless, there are various heuristics for trying to find a good variable ordering, and in real-world problems, they often work reasonably well.

So, your problem can be framed as the problem of choosing the optimal variable ordering to represent your sets as a BDD.

ZDDs are a variant of BDDs that are better in some circumstances.  ZDDs are especially oriented at representing a set of sets, so they might be particularly helpful for your needs.  ZDDs are especially handy if you need to represent a bunch of sets that are related to each other in some way; ZDDs provide a compact and efficient encoding for that situation.