1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\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$ – Gareth Rees 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