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.


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.

  • $\begingroup$ Hi Kyle, thanks so much for the help. How does what you did above differ from what I will need to do to solve the original problem? I'm sorry if this is a simple question.. I'm still quite confused. Thanks so much again. $\endgroup$
    – user221400
    May 14 '15 at 4:29
  • $\begingroup$ @OliviaP.: Kyle has given an example showing how to reduce one particular instance of Exactly-One-in-3SAT to an instance of Unit Intersection. You should generalize this example into a proof that every instance of Exactly-One-in-3SAT can be reduced to an instance of Unit Intersection. You'll probably want to prove that the Unit Intersection really maps back to a solution for the instance of Exactly-One-in-3SAT. You'll also need to figure out how to deal with repeated literals in clauses. $\endgroup$ May 14 '15 at 14:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy