Proving UNIT INTERSECTION NP-complete

Question

I am working on some review problems right now and am extremely stuck on how to solve problem - 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 solve this problem, but am so stuck right now. Thank you in advance for any help.

Answer 1

Your intuition for a good problem to use for NP-complete reduction is on the mark. Given a 3-SAT formula, with $m$ variables, add clauses $(x_i$ OR (NOT $x_i$)) for each variable $x_i$. Then for each clause, create the two or three element subset $S_j$ where the elements are variables or negations of variables appearing in the clause, which are considered distinct elements. Then let $X$ be the union of all the elements (variables and negations of variables). If you ever choose a variable AND its negation as elements of $T$, then there will be a clause that has intersection with $T$ of size 2 or more. So in order for $T$ to have intersection of size 1 with every subset, only one variable $x_i$ or its negation is chosen to be an element of $T$ (but not both). Thus this will give you a satisfying assignment to your original Exactly-One-3SAT problem.

Answer 2

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.