A family of sets $F = \{S_1, \dots, S_n\}$ on the ground set $S$ is laminar, if for every $1\leq i < j \leq n$, either $S_i \subsetneq S_j$ or $S_j \subsetneq S_i$ or $S_i \cap S_j = \varnothing$ and also for every $1 \leq i \leq n: \varnothing \neq S_i \subseteq S$.

The question is given a family of sets $F = \{S_1, \dots, S_n\}$, find laminar family $F' = \{S'_1, \dots, S'_n\}$ so that for each i we have $S_i \subseteq S'_i$ and $\sum_i |S'_i - S_i|$ is minimized. In other words we want to find the smallest extension of $F$ which is laminar.

Note that there may be no such extension for $F$. For example if for $i\neq j$ we have $S_i = S_j = S$ then there exist no laminar extension for $F$. Is there any efficient algorithm for finding the smallest laminar extension of $F$?



Your Answer

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

Browse other questions tagged or ask your own question.