Tag Archives: Difficulty 7

Generalized Kayles

I hadn’t heard of this game before encountering this problem.  It sort of feels a lot like Nim to me.

The problem: Generalized Kayles.  This is problem GP3 in the appendix.

The description: Given a graph G=(V,E). Players take turns removing vertices and all vertices adjacent to it from the graph.  The first player to have no vertices left loses.

Example: Here’s a graph:

Suppose player 1 chooses vertex c.  Then we also remove s,b, d, and t.  All that is left are vertices a and e.  Whichever vertex player 2 chooses, player 1 can choose the other one, and win.

Reduction: This one is again by Schaefer, and again uses the same problem which is either Sequential Truth Assignment or QBF, depending on how you look at it.

Just like last time, we’re given a formula: (∃ x1) (∀ x2) (∃ x3) … (∃ xn) (A1 ∧ A2 ∧ … Am), where each Ai is a disjunction of literals.  We’ll further assume n is odd (so the last quantifier is ∃).  The graph is built as follows:

  • Each clause k in the formula gets a vertex x0,k.  These vertices are all connected to each other.
  • Each variable xi in the formula gets two vertices: xi and ~xi, that have an edge between them. We also get y vertices: yi,j for all j 0 <= j < i
  • We add an edge between xi and x0,k if xi appears as a literal in clause k.  Similarly, we add an edge between ~xi and x0,k if ~xi appears as a literal in clause k.
  • Each yi,j vertex connects to all xk vertices where k <= i.  Each yi,j vertex also connects to all ya,b vertices where a < i and b < a.

Here’s a picture from the paper of what we get:

One main point that comes out of this construction is that players need to take their first n moves playing the x (or ~x) vertices in order.  If you go out of order, the opponent can play a y vertex and remove everything.  If you play a y vertex, the opponent can play an x vertex (or an x0 vertex) and remove everything.

If the original formula was satisfiable, player 1 (who is the ∃ player) starts by choosing either x1 or ~x1.  No matter which of x2 or ~x2 is chosen by the opponent (the ∀ player), player3 will have a way to set x3 to keep the formula satisfiable.  This process continues for all variables.  Once player 1 plays the last variable (xn or ~xn), all vertices have been removed from the graph- most importantly, all of the x0 vertices have been removed, because there is an edge from each one to each variable whose setting would satisfy the clause.  Thus, player 2 has no place to play, and player 1 wins.

If the formula is not satisfiable, then after taking turns choosing xi or ~xi for all i, there is still some x0 vertex in the graph (corresponding to a clause not satisfied by the variable choices made).  Player 2 can select that vertex, removing all x0 vertices from the graph, and will win.

Difficulty: 7.  I can see what the “jobs” of each vertex are: The xi  set the truth values of a variable, the x0 ensure that each clause is satisfied by a variable setting, and the y vertices are there to force players to choose the xi vertices in order.  I don’t think I could have come up with this though.

 

Generalized Geography

It’s spring break here- I was expecting to take the week off, but got this post done anyway.  This might mean I skip next week though.

The problem: Generalized Geography.  This is problem GP2 in the appendix.

The description: Given a directed graph G=(V,A) and a starting vertex vo.  Players alternate choosing edges that leave the current vertex (starting with v0.  The next current vertex is the one at the end of the edge leaving from vo.  You can’t choose an edge that is already chosen.  The first player to be unable to choose an edge loses.  Does Player 1 have a forced win?

Example: This is the “geography” game kids play in the car, where you have to think of a place that has as its first letter the last letter of the previous choice.  As a graph problem, vertices correspond to letters, and edges to locations:

Note that the vertices can have self-loops, and (at least in the actual game) could have multiple edges between pairs of vertices.  There is no requirement to have any edges leave a vertex either- I remember instituting the “Phoenix rule”  on car trips because nobody could think of a place that started with X.

Anyway, if we start at E, player 1 has a forced win- they have to take “Egypt” to T, and then player 2 has to take “Texas” to S, and if player 1 chooses “Singapore” we’re in vertex E, it’s player 2’s turn, and they have no place left to pick.  (The actual game has many more edges, of course)

Reduction:  Schaefer says he’s building off of the Sequential Truth Assignment problem from last time, but his instance looks more like an instance of QBF. (I think this is a result of his claim that they’re basically the same problem).  So we’re given a formula: (∃ x1) (∀ x2) (∃ x3) … (∃ xn) (A1 ∧ A2 ∧ … Am), where each Ai is a disjunction of literals.  We’ll further assume n is odd (so the last quantifier is ∃)

We then go on to build a graph.  Each positive and negative literal gets a vertex.  Each variable x1 gets 4 vertices in the graph:

  • xi corresponding to a positive literal
  • ~xi corresponding to a negative literal
  • 2 vertices u and v that control the “entrance” and “exit” for the setting of one of the 2 literal values.

We have a vertex for each clause (yi), and an additional vertex un+1 so the last vi has someplace to go.

Each set of these 4 vertices are set up in a diamond, with edges from ui to both xi and ~xi, and then from both of those to vi. vi then connects to ui+1, making a chain of diamonds. The final un+1 connects to each y vertex, and each y vertex connects to the literals that are in its clause.

Here’s the example picture from the paper:

Player 1 starts on vertex u1. The player chooses whether to make variable x1 positive or negative by going to that vertex (simulating a “there exists”), and player 2 has no choice but to move on to the v1 vertex, and player 1 has no choice to move to the next u2 (simulating a “for all”). This alternating process continues until we hit vertex un+1.  Since there are an odd number of variables, it is now player 2’s turn.

If the setting of the variables has not satisfied some clause, player 2 can move to the y vertex of that unsatisfied clause.  Then player 1 has to go to one of the 3 literals that appear in that clause.  Since the clause was not satisfied, all of these variables have not been chosen, so the edge from that literal to the v vertex is available for player 2 to pick.  But after that, the vertex from the v vertex to the next u vertex has already been chosen, so player 1 loses.

If the setting of the variables has satisfied every clause, then player 2 has to pick a move to a y vertex that has a literal chosen by a player to satisfy it. When player 1 moves to that vertex, the only edge exiting that vertex has already been chosen, so player 2 loses.

Difficulty: 7. I think this is very slick and elegant, but I don’t see a student getting there without lots of help.

Protected: Simultaneous Divisibility of Linear Polynomials

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

Protected: Simultaneous Incongruences

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

Protected: Integer Knapsack

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

Protected: Resource Constrained Scheduling

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

Protected: Single Execution Time Scheduling With Variable Number of Processors

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

Protected: Sequencing With Deadlines and Setup Times

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

Serializability of Database Histories

This is another problem with a cool elegant reduction once you get past the baggage you need to know to understand the problem.  This database section seems to be full of problems like these.

The problem: Serializability of Database Histories.  This is problem SR33 in the appendix.

The description: We have a set V of variables in our database, and a set T of transactions, where each transaction i has a read operation (Ri) that reads some subset of V, and a write operation Wi that writes some (possibly different) subset of V.  We’re also given a “history” H of T, which permutes the order of all reads and writes maintaining the property that for all i, Ri comes before Wi in the history.  Think of this as a set of parallel transactions that reach a central database.  H is the order the database processes these operations.

Can we find a serial history H’ of T, with the following properties:

  • Each Ri occurs immediately before its corresponding Wi.
  • A “live transaction” is a transaction (Ri, Wi) where either Wi is the last time a variable is written before the Rj of some other live transaction or the last time the variable is written at all.  The set of live transactions in H and H’ needs to be the same.
  • For each pair of live transactions (Ri, Wi) and (Rj, Wj), for any variable v in Wi∩Rj, Wi is the last write set to contain v before Rj in H if and only if Wi is the last write set to contain v before Rj in H’.  The paper says that this means transaction j “reads from” (or “reads v from”) transaction i.

Example: The paper by Papadimitriou, Bernstein, and Rothnie that has the reduction has a good simple example of a non-serializable history:

H= <R1, R2, W2, W1>, where R1 and W2 access a variable x, and R2 and W1 access a variable y.  Both transactions are live since they both write their variables for the last time.  Notice that neither transaction reads any variable.  But the two possible candidates for H’ are: <R1, W1, R2, W2> (where R2 reads the y written by W1) and <R2, W2, R1, W1> (where R1 reads the x written by W2), so neither H’ candidate has the same set of transactions reading variables from each other.

Reduction: Is from Non-Circular Satisfiability.  Given a formula, they generate a “polygraph” of a database history.  A polygraph (N,A,B) is a directed graph (N,A) along with a set B of “bipaths” (paths that are 2 edges long).  If a bipath{(v,u), (u,w)} is in B, then the edge (w,v) is in A.  So, if a bipath exists in B from v to w, then an edge in A exists from w back to v.  This means that we can view a polygraph (N,A,B) as a family of directed graphs.  Each directed graph in the family has the same vertices and an edge set A’ that is a superset of A and contains at least one edge in each bipath in B. They define an acyclic polygraph as a polygraph (represented as a family of directed graphs) where at least one directed graph in the family is acyclic.

In the paper, they relate database histories to polygraphs by letting the vertex set N bet a set of live transactions.  We build edges in A (u,v) from transactions that write a variable (vertex u)  to transactions that read the same variable (vertex v).  If some other vertex w also has that variable in their read set then the bipath {(v,w), (w,u)} exists in B.  So edges (u,v) in A mean that u “happens before” v since u writes a variable that v reads.  A bipath {(v,w), (w,u)} means that w also reads the same variable, so must happen before u or after v.  They show that a history is serializable if and only if the polygraph for the history is acyclic.

So, given a formula, they build a polygraph that is acyclic if and only if the formula is satisfiable.  The polygraph will have 3 vertices (aj, bj, and cj) for each variable xj in the formula.  Each a vertex connects by an edge in A to its corresponding B vertex.  We also have a bipath in B from the b vertex through the corresponding c vertex back to the a vertex.

Each literal Cik  (literal #k of clause i) generates two vertices yik and zik.  We add edges in A from each yik to zi(k+1)mod 3  (in other words, the y vertex of each clause connects to the “next” z vertex, wrapping around if necessary).  If literal Cik is a positive occurrence of variable Xj, we add edges (cj, yik) and (bj, zik) to A, and the bipath {(zik, yik), (yik, bj)} to B.  If the literal is negative, we instead add (zik, cj) to A and {(aj, zik), (zik, yik)} to B.

If the polygraph is acyclic (and thus the history it represents is serializable), then there is some acyclic digraph in the family of directed graphs related to the polygraph.  So the bipath {(bj, cj), (cj, aj)} will have either the first edge from b-c (which we will represent as “false”) or will have the second edge from c-a (which we will represent as “true”).  (The directed graph can’t have both because its edges are a superset of A, which means it has the edge (aj, bj) and taking both halves of he bipath will cause a cycle).

If our acyclic directed graph has the “false” (b-c) version of the edge for a literal, then it also has to have the z-y edge of the bipath associated with the literal (otherwise there is a cycle).  If all of the literals in a clause were set to false, this would cause a cycle between these bipath edges and the y-z edges we added in A for each clause.  So at least one literal per clause must be true, which gives us a way to satisfy the formula.

If the formula is satisfiable, then build the acyclic digraph that starts with all of A, and takes the bipath edges corresponding to the truth value of each variable, as defined above.  This implies ways you need to take the edges from the bipaths for the literals, to avoid cycles.  The only way now for the graph to be acyclic is for there to be a cycle of x’s and y’s in the edges and bipath edges.  But that would imply that we’ve set all of the literals in a clause to false. Since we know that the clause can be made true (since the original formula is satisfiable), we know that a way exists to make the directed graph acyclic.

Difficulty: 7.  It takes a lot of baggage to get to the actual reduction here, but once you do, I think it’s pretty easy and cool to see how the cycles arise from the definitions of the graphs and from the formula.

Protected: Tableau Equivalence

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