I am extremely stuck on how to go about this problem and any help would be so appreciated. We are told to consider the following combinatorial problem:
Unit Intersection: Let X = {1, 2,…,n}. Given a family of subsets $S_1,…,S_m$ of X,
determine whether there is a subset T of X such that for all i,|T ∩ $S_i$| = 1 ?
I am then trying to prove that Unit Intersection is NP-complete using a reduction from Exactly-One-3SAT. In the Exactly-One-3SAT problem, we are given a 3CNF formula, and need to decide whether there is an assignment to the variables such that every clause contains exactly one true literal. In a 3CNF formula, every clause has at most three literals. A clause in a 3CNF formula may contain repeated literals.
I've been working for hours trying to find a way to even start this problem, but am so stuck right now. Thank you in advance for any help.
Best Answer
The reduction is straightforward. As an example, I'll reduce an instance of Exactly-One-in-3SAT to an instance of Unit Intersection.
$$ (x_1 \lor x_4 \lor x_3) \land (\overline{x_4} \lor \overline{x_2} \lor x_3) \land (x_2 \lor x_1 \lor \overline{x_3}) $$
Let $n$ be the number of distinct (positive and negative) literals in the formula, and choose a bijection between the literals and the integers from $1$ to $n$:
$$x_1 ↔ 1\\ x_2 ↔ 2\\ x_3 ↔ 3\\ x_4 ↔ 4\\ \overline{x_2} ↔ 5\\ \overline{x_3} ↔ 6\\ \overline{x_4} ↔ 7$$
The integers on the right are the set $X$ in the Unit Intersection instance: $X = \lbrace 1,2,3,4,5,6,7 \rbrace$.
Convert each clause in the Exactly-One-in-3SAT instance into a set of integers by using the mapping created earlier to replace literals with integers.
$$ (x_1 \lor x_4 \lor x_3) \rightarrow \lbrace 1, 4, 3 \rbrace \\ (\overline{x_4} \lor \overline{x_2} \lor x_3) \rightarrow \lbrace 7, 5, 3 \rbrace \\ (x_2 \lor x_1 \lor \overline{x_3}) \rightarrow \lbrace 2, 1, 6 \rbrace$$
These are the initial subsets $S_1 ... S_m$ in the Unit Intersection instance.
If variables appear as both positive and negative literals in the Exactly-One-in-3SAT instance, for each such variable add a subset that contains the mapped integers for the positive and negative literals of that variable. For our instance we would add
$$\lbrace 2, 5 \rbrace \\ \lbrace 3, 6 \rbrace \\ \lbrace 4, 7 \rbrace$$
The reduction is complete. If a subset $T$ can be found for the Unit Intersection instance, that solution can be mapped back to a satisfying assignment for the Exactly-One-in-3SAT instance.