Tag Archives: Difficulty 3

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.

 

Protected: Quantified Boolean Formulas

This content is password protected. To view it please enter your password below:

Protected: Integer Programming

This content is password protected. To view it please enter your password below:

Protected: Three-Way Matching of Integers

This content is password protected. To view it please enter your password below:

Protected: Knapsack

This content is password protected. To view it please enter your password below:

Protected: Sequencing to Minimize Tardy Tasks, Sequencing to Minimize Tardy Task Weight

This content is password protected. To view it please enter your password below:

Protected: Sequencing With Release Times and Deadlines

This content is password protected. To view it please enter your password below:

Protected: Non-Circular Satisfiability

This content is password protected. To view it please enter your password below:

Protected: Conjunctive Boolean Query

This content is password protected. To view it please enter your password below:

Protected: Ratio Clique

This content is password protected. To view it please enter your password below: