Alternating Hitting Set

I think this might be the last of the problems we do from the Schaefer paper we’ve used so much recently.

The problem: Alternating Hitting Set.  This is problem GP7 in the appendix.

The description: Given some universe set B, and a collection C of subsets of B.  Players take turns choosing an element from B.  Once enough elements are chosen to make all sets in C have at least one element chosen, the player who made that move loses.  Does player 1 have a forced win?

Example: Let B= {1,2,3}, and C = {{1,2,3}, {2,3}, {1,3}, {1,2}}.  Player 1 can win by choosing 1, which hits all sets in C except {2,3}.  Since player 2 has to pick either a 2 or 3, they will hit that set and lose.

Reduction: Schaefer remarks that this is just a special case of Variable Partition Truth Assignment. with sets instead of variables.  Here’s how that goes:

Suppose we have an instance of Variable Partition Truth Assignment, so a CNF formula with all positive variables.  We just create a set B with one element per variable, and the clauses become the sets in C.  Then picking an element of B is the same as setting a variable to true.  Hitting a set in C is the same as making the clause true.

Difficulty: 3.  Maybe this problem is close enough to Variable Partition Truth Assignment that it didn’t need its own article.  On the other hand, it’s nice to see an easy reduction for once.


Leave a Reply

Your email address will not be published. Required fields are marked *