<p>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.</p>
<p>Let <span class="math-container">$\varphi = C_1 \land \dots \land C_m$</span> be a 3CNF formula in which the variables <span class="math-container">$\{x_0,\dots,x_{n-1}\}$</span> occur. Consider the following family <span class="math-container">$\mathcal{A}$</span> of subsets of <span class="math-container">$\{0,\dots,2n - 1\}$</span>. First, for every <span class="math-container">$0\leq i \leq n-1$</span> we add the set <span class="math-container">$\{2i,2i+1\}$</span> to <span class="math-container">$\mathcal{A}$</span>. Then, for every clause <span class="math-container">$C_k = (\ell_1 \lor \ell_2 \lor \ell_3)$</span> we add the set <span class="math-container">$\{i_1,i_2,i_3\}$</span>, where <span class="math-container">$i_j$</span> is <span class="math-container">$2i$</span>, if <span class="math-container">$\ell_j = x_i$</span>, and <span class="math-container">$2i+1$</span>, if <span class="math-container">$\ell_j = \neg x_i$</span>. We now claim that <span class="math-container">$\mathcal{A}$</span> has the choosability property iff <span class="math-container">$\varphi$</span> has a truth assignment to the variables <span class="math-container">$\{x_0,\dots,x_{n-1}\}$</span> so that each clause has exactly one true literal.</p>
<p>Suppose first that there exists <span class="math-container">$R \subseteq \{0,\dots,2n - 1\}$</span> such that for every <span class="math-container">$B \in \mathcal{A}$</span> we have that <span class="math-container">$|R \cap B| = 1$</span>. Since we added <span class="math-container">$\{2i,2i+1\}$</span> to <span class="math-container">$\mathcal{A}$</span>, for every <span class="math-container">$0 \leq i \leq n - 1$</span>, <span class="math-container">$R$</span> encodes the following truth assignment to the variables <span class="math-container">$\{x_0,\dots,x_{n-1}\}$</span>: <span class="math-container">$s(x_i) = 1$</span> if <span class="math-container">$2i \in R$</span> and <span class="math-container">$s(x_i) = 0$</span> if <span class="math-container">$2i+1 \in R$</span>. Note that <span class="math-container">$R$</span> can be viewed as the set of literals that <span class="math-container">$s$</span> makes true. Now we claim that <span class="math-container">$s$</span> makes exactly one literal in each clause of <span class="math-container">$\varphi$</span> true: but this just follows from the fact that <span class="math-container">$|R \cap \{i_1,i_2,i_3\}| = 1$</span>, for every <span class="math-container">$\{i_1,i_2,i_3\} \in \mathcal{A}$</span>.</p>
<p>Conversely, if there exists a truth assignment <span class="math-container">$s$</span> to the variables <span class="math-container">$\{x_0,\dots,x_{n-1}\}$</span> so that each clause has exactly one true literal, then we can define
<span class="math-container">$$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\}. $$</span>
Clearly <span class="math-container">$R$</span> has the desired properties.</p>

CC BY-SA 4.0
2022-06-07T11:52:46.287Z
2022-06-07T12:46:45.653Z
2022-06-07T12:46:45.653Z
Reijo Jaakkola
<p>Let <span class="math-container">$n\in\mathbb{N}$</span> be a positive integer, and let <span class="math-container">${\cal A}$</span> be a collection of subsets of <span class="math-container">$n=\{0,\ldots,n-1\}$</span>. We say <span class="math-container">${\cal A}$</span> has the <em>choosability property</em> if there is <span class="math-container">$R\subseteq n$</span> such that <span class="math-container">$|R\cap B|=1$</span> for all <span class="math-container">$B\in {\cal A}$</span>.</p>
<p>Given <span class="math-container">$n\in \mathbb{N}$</span> and <span class="math-container">${\cal A}\subseteq {\cal P}(n)$</span>, is the problem of deciding whether <span class="math-container">${\cal A}$</span> has the choosability property, NP-hard?</p>

CC BY-SA 4.0
2022-06-07T11:57:43.843Z
Isn't there an easy reduction from 3D-matching?
Neal Young
<np-hardness><np-complete>
Is "choosability of subsets" NP-hard?
Dominic van der Zypen
# Is "choosability of subsets" NP-hard?

(Asked by: username_0 on 2022-06-07)

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?

**Tags:** np-hardness, np-complete

> **Comments:**
> **username_1**: Isn't there an easy reduction from 3D-matching?  

---

## 1 answers

### Answer by username_2 on 2022-06-07. Score: 1

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.


---

