0
$\begingroup$

Let $n\in\mathbb{N}$ be a positive integer, and let ${\cal A}$ be a collection of subsets of $n=\{0,\ldots,n-1\}$. We say ${\cal A}$ has the choosability property if there is $R\subseteq n$ such that $|R\cap B|=1$ for all $B\in {\cal A}$.

Given $n\in \mathbb{N}$ and ${\cal A}\subseteq {\cal P}(n)$, is the problem of deciding whether ${\cal A}$ has the choosability property, NP-hard?

$\endgroup$
1
  • $\begingroup$ Isn't there an easy reduction from 3D-matching? $\endgroup$
    – Neal Young
    Jun 7, 2022 at 11:57

1 Answer 1

1
$\begingroup$

Yes, and one can give a reduction from one-in-three 3SAT, which is the following problem: given a conjunctive normal form with three literals per clause, the problem is to determine whether there exists a truth assignment to the variables so that each clause has exactly one true literal.

Let $\varphi = C_1 \land \dots \land C_m$ be a 3CNF formula in which the variables $\{x_0,\dots,x_{n-1}\}$ occur. Consider the following family $\mathcal{A}$ of subsets of $\{0,\dots,2n - 1\}$. First, for every $0\leq i \leq n-1$ we add the set $\{2i,2i+1\}$ to $\mathcal{A}$. Then, for every clause $C_k = (\ell_1 \lor \ell_2 \lor \ell_3)$ we add the set $\{i_1,i_2,i_3\}$, where $i_j$ is $2i$, if $\ell_j = x_i$, and $2i+1$, if $\ell_j = \neg x_i$. We now claim that $\mathcal{A}$ has the choosability property iff $\varphi$ has a truth assignment to the variables $\{x_0,\dots,x_{n-1}\}$ so that each clause has exactly one true literal.

Suppose first that there exists $R \subseteq \{0,\dots,2n - 1\}$ such that for every $B \in \mathcal{A}$ we have that $|R \cap B| = 1$. Since we added $\{2i,2i+1\}$ to $\mathcal{A}$, for every $0 \leq i \leq n - 1$, $R$ encodes the following truth assignment to the variables $\{x_0,\dots,x_{n-1}\}$: $s(x_i) = 1$ if $2i \in R$ and $s(x_i) = 0$ if $2i+1 \in R$. Note that $R$ can be viewed as the set of literals that $s$ makes true. Now we claim that $s$ makes exactly one literal in each clause of $\varphi$ true: but this just follows from the fact that $|R \cap \{i_1,i_2,i_3\}| = 1$, for every $\{i_1,i_2,i_3\} \in \mathcal{A}$.

Conversely, if there exists a truth assignment $s$ to the variables $\{x_0,\dots,x_{n-1}\}$ so that each clause has exactly one true literal, then we can define $$R = \{2i \mid 0 \leq i \leq n - 1 \text{ and } s(x_i) = 1\} \ \cup \ \{2i+1 \mid 0 \leq i \leq n - 1 \text{ and } s(x_i) = 0\}. $$ Clearly $R$ has the desired properties.

$\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.