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

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.

• Since $\beta$ is increasing, then surely condition 1 is satisfied, isn't it? And since it is increasing, then also it means that condition 2 implies there are no elements from $Y$ or there are no elements from $X$. What am I missing here? Jan 6 at 14:03
• Given condition 1, condition 2 can be reduced to that the last set in $\beta|_{\mathcal{X}}$ does not intersect with all sets in $\beta|_{\mathcal{Y}}$, as noted by @pcpthm. Jan 6 at 14:30
• @nirshahar $\beta$ is not necessarily increasing. For example, if $X_1 = \{0,2\}$, $X_2 = \{0\}$, $X_3 = \{0, 2, 4\}$ and $Y_1 = \{1\}$, $Y_2 = \{1, 2\}$, $Y_3 = \{1,3\}$, then in the sequence $\alpha = (X_1, Y_1, X_2, Y_2, X_3, Y_3)$, $\beta = (X_1, Y_1, X_3, Y_3)$ is a valid solution if I understand correctly. (I agree that the wording is ambiguous, with the "with respect to $\alpha$") Jan 7 at 6:06

## 1 Answer

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.