Given a collection C of sets, there are a number of proposed algorithms for building the subset partial order, e.g. this paper.

But is there any work on algorithms that return the [components of such collection, that is the weakly connected components of the DAG that represents the subset relation?

  • Input: C, a set of sets of elements.
  • Output: P, a partitioning of C, that is a set of sets of sets of elements such that all sets in a partition are connected by the subset relation and no sets from different partitions are connected.

Regarding Input and Output, this problem is really simple and has many potential applications, but I have not been able to find any research that is looking for optimal solutions.

Of course, you can build the partial order by above methods and then use a union-find structure to compute the components, but aren't there any shortcuts for the described problem? In particular it would be good to skip the explicit computation of all edges.

Also if memory would be taken into account, that would be great.

Any ideas?

I am currently looking into the following approach:

  1. Compute the relationships between all the sets in C and their minimal elements in C as in this paper
  2. Compute the connected components of this reduced poset in linear time

So in this context, I am looking for a simple algorithm for finding the minimal elements in a poset that exploits the fact that the partial order is the subset partial order, which will probably allow for shortcuts compared to any given partial order, i.e. see this paper.



Your Answer

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