3
$\begingroup$

I have a list of sets $L$. I want to partition the sets in $L$ to produce a new list $L'$ that is a Laminar Set Family

Concretely:


For any $L'_i, L'_j \in L'$ if $L'_i \not\subseteq L'_j$ and $L'_j \not\subseteq L'_i$ then $L'_i \cap L'_j \equiv \varnothing$.


I want a minimal length $L'$ (which is equivalent to saying I want to perform the fewest of partitions of sets in $L$). Note that this is a list of sets, not a set of sets, so duplicates do count against the optimization objective.

As a concrete example, if $L = [\{a\},\{b,c\},\{a,b,c\},\{a,c,d\}]$ then the minimal $L' = [\{a\},\{b\},\{c\},\{a,b,c\},\{a,c\},\{d\}]$ formed by partitioning $\{b,c\}$ into $\{b\},\{c\}$, and $\{a,c,d\}$ into $\{a,c\},\{d\}$.

The list $L'' = [\{a\},\{b,c\},\{a\},\{b,c\},\{a\},\{c\},\{d\}]$ is not a minimal solution even though it has fewer unique sets, because it has a larger number of total sets.


EDIT2: This is a sub-problem of the following problem that came up in my work. This is an original problem of which I have not found any previous statement.

We have a directed-hyper-forest $F$. Each node $v$ has a set of values $S_v$ associated with it. Each hyper-edge $e: v \rightarrow C_e$ is labeled with a non-strict subset of the values of it's parent $S_v$, (call it $S_e$).

For a value $s \in S_v$, we say the adjacency set of an "assignment" of $s$ to $v$, $C_s$ is the union over all $C_e$, where $s \in S_e$.

An assignment of values to nodes $A$ contains at most one $(s, v) \in (S_v, F)$ pair for each $v \in F$. We call an assignment $A$ valid if for any node value pair $(s, v)$, an assignment exists for a child $c$ of $v$ if and only if $c \in C_s$.

Now the actual problem: how can I convert $F$ to some (minimal, non-hyper) finite state machine $G$ such that any node in $g \in G$ is "labeled" with exactly one $v$, and has transitions that are a non-strict-subset of $S_v$.

This FSM must also have the property that for any valid assignment $A$, we can traverse $G$ using the choices in $A$, and see exactly one node $g$ "labeled" with $v$ for each $v$ with an assignment in $A$. In other words, some permutation of $A$ must be a valid traversal of $G$ by replacing each $v \in A$ with some $g$ that is labeled with $v$.

How does this relate to the problem I mentioned above? Well if we can split the children of $v$ into a laminar set family based on the hyper edges connecting them to $v$, then we can build a FSM where transitions follow containment, then we can make transitions from $v$ on a single value $s$ to the minimal set containing $s$, and be sure that after following all the containment transitions we will never traverse a node that does not contain s. We can use this to recursively build up a FSM with our desired property. This is just one such approach but I'm happy to discuss others.

EDIT: In an earlier revision I provided a wrong algorithm. Deleting it for brevity.

$\endgroup$
  • $\begingroup$ So, do you want an efficient provably-correct algorithm OR wanna improve and finish your algorithm? $\endgroup$ – Thinh D. Nguyen Nov 1 '18 at 0:47
  • $\begingroup$ I want a provably correct algorithm. Don't care so much about efficiency, since the lists involved are fairly small (an $O(n^n!)$ algorithm would be a problem, but not e.g. something exponential). I do care deeply about the length of $L'$ so I want to know I'm getting the shortest $L'$ possible. Whether or not you improve on my algorithm or not is a matter of how close I am to a good solution. I don't know if my hunch is correct or not. $\endgroup$ – Eli Bixby Nov 1 '18 at 0:50
  • $\begingroup$ This question is attracting more attention. If it comes from an online course or contest or article, please add a URL in the question. If it comes from a book or a paper, a reference. If it comes from your personal life or work, some background or motivation. Besides paying proper attribute to the original source, all that information motivates and helps more people answer your question faster and better. $\endgroup$ – Apass.Jack Nov 3 '18 at 18:19
  • $\begingroup$ It is particular important to check whether we have missed a more basic, or more important, or more interesting question, before people should spend time in answering a seemingly big question. $\endgroup$ – Apass.Jack Nov 3 '18 at 18:23
  • $\begingroup$ @Apass.Jack I've added the full problem I'm trying to solve for context. Perhaps there is some solution to the full problem that does not involve trying to solve the subproblem I have mentioned, but I would be surprised by that. $\endgroup$ – Eli Bixby Nov 5 '18 at 18:42

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.