# Is "choosability of subsets" NP-hard?

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?

• Isn't there an easy reduction from 3D-matching? Jun 7, 2022 at 11:57

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.