To transform 3CNF to an instance of Hitting set, we use the following procedure:
Now I would love an example of how to do this, since I am a bit confused. I tried the following:
I used this 3CNF formula:
Now for every positive literal we need to add an element to the set S. However as stated in the approach it says that for literal x_j we need to add element u_j. What is this element u_j? In my example we can use the assignment a = 1, b = 0, c = 1, d = 1 which satisfies the formula. Now when we look at the first clause C_i, the first positive literal is a. so now we need to add something to the set S_i but I don't know what.
Beforehand it is stated that we need to construct the set U. But then how is u_j related with a literal? I can't see the logic in this and an example would make it a lot clearer.
Another question, it says for each positive literal, when is a literal positive? Simply when there's no NOT sign or whenever it equals to 1 after giving the literals an assignment?
Thanks!