2
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ 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? $\endgroup$
    – nir shahar
    Jan 6 at 14:03
  • 1
    $\begingroup$ 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. $\endgroup$
    – Mengfan Ma
    Jan 6 at 14:30
  • $\begingroup$ @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$") $\endgroup$
    – Nathaniel
    Jan 7 at 6:06

1 Answer 1

2
$\begingroup$

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.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.