There are two types of sets $\mathcal{X} = \{X_{1}, X_{2}, \ldots, X_{n_{1}} \}$ and $\mathcal{Y} = \{Y_{1}, Y_{2}, \ldots, Y_{n_{2}}\}$ such that $X_i, Y_j \subseteq [m]=[\mathrm{poly}(n)]$ and $n = n_{1} + n_{2}$. Given a sequence $\alpha$ over $\mathcal{X} \cup \mathcal{Y}$, the goal is to find the longest (increasing with respect to $\alpha$) sub-sequence $\beta$ such that
- the sub-sequence $\beta$ restricted to $\mathcal{X}$ is a sequence of nested sets, that is $\left. \beta \right|_{\mathcal{X}} = (X_{i_{1}}, X_{i_{2}}, \ldots, X_{i_{\ell}})$ satisfies that $X_{i_{1}} \subseteq X_{i_{2}} \subseteq \cdots \subseteq X_{i_{\ell}}$.
- These two sub-sequences $\left. \beta \right|_{\mathcal{X}}$ and $\left. \beta \right|_{\mathcal{Y}}$ have no common elements, that is, for every pair of sets $X_{i}, Y_{j}$ in $\beta$, $X_{i} \cap Y_{j} = \varnothing$.
Is (the decision version of) this problem NP-hard, or can it be solved in polynomial time (with respect to $n$)?
For the special case, if $\mathcal{Y}$ is empty, this problem can be solved by using dynamic programming in polynomial time.