Is this varient of longest increasing nested sets problem NP-hard？

Question

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

1. 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}}$.
2. 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.

Answer 1

This problem is polynomial-time solvable.

Suppose we know the last selected $X_\ell$. Then, remove all $Y$s that have a non-empty intersection to $X_\ell$. Now, we don't have to check for the second condition anymore because we have $X_i \cap Y_j \neq \emptyset \implies X_\ell \cap Y_j \neq \emptyset$ by the first condition $X_i \subseteq X_\ell$. Therefore, we reduced the problem to $n_1$ subproblems of the already-known polynomial-time solvable case of when $\mathcal{Y}$ is empty.