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
    Commented Jan 6, 2023 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
    Commented Jan 6, 2023 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
    Commented Jan 7, 2023 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 you have read our privacy policy.

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