Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

At my local squash club, there is a ladder which works as follows.

  1. At the beginning of the season we construct a table with the name of each member of the club on a separate line.
  2. We then write the number of games won and the number of games played next to each name (in the form: player wins/games).

Thus at the beginning of the season the table looks like this:

Carol 0/0
Billy 0/0
Alice 0/0
Daffyd 0/0

Any two players may play a match, with one player winning. If the player nearest the bottom of the table wins, then the position of the players is switched. We then repeat step 2., updating the number of wins and games next to each player. For example, if Alice beats Billy, we have

Carol 0/0
Alice 1/1
Billy 0/1
Daffyd 0/0

These matches go on throughout the season and eventually result in players being listed in approximate strength order.

Unfortunately, the updating happens in a rather haphazard way, so mistakes are made. Below are some examples of invalid tables, that is, tables which could not be produced by correctly following the above steps for some starting order (we have forgotten the order we used at the beginning of the season) and sequence of matches and results:

Alice 0/1
Billy 1/1
Carol 0/1
Daffyd 0/0

Alice 2/3
Billy 0/1
Carol 0/0
Daffyd 0/0

Alice 1/1
Billy 0/2
Carol 2/2
Daffyd 0/1

Given a table, how can we efficiently determine whether it is valid? We could start by noting the following:

  1. The order of the names doesn't matter, since we have forgotten the original starting order.

  2. The total number of wins should be half the sum of the number of games played. (This shows that the first example above is invalid.)

  3. Suppose the table is valid. Then there is a multigraph - a graph admitting multiple edges but no loops - with each vertex corresponding to a player and each edge to a match played. Then the total number of games played by each player corresponds to the degree of the player's vertex in the multigraph. So if there's no multigraph with the appropriate vertex degrees, then the table must be invalid. For example, there is no multigraph with one vertex of degree one and one of degree three, so the second example is invalid. [We can efficiently check for the existence of such a multigraph.]

So we have two checks we can apply to start off with, but this still allows invalid tables, such as the third example. To see that this table is invalid, we can work backwards, exhausting all possible ways the table could have arisen.

I was wondering whether anyone can think of a polynomial time (in the number of players and the number of games) algorithm solving this decision problem?

share|improve this question
2  
Perhaps there is a Havel Hakimi type theorem for directed multigraphs... –  Aryabhata Sep 20 '12 at 3:27
    
Why can the third example not be possible? What if Alice won over Bob, Carol won over Bob and Carol won over Daffyd. Then Alice won 1 out of 1 games, Bob won 0 of 2 games, Carol won 2 of 2 games and Daffyd won 0 of 1 games? –  utdiscant Sep 24 '12 at 4:53
    
utdiscant: After each game, if the lower player wins, the players are switched. To show that the third example is possible, you would need to give a starting configuration and a sequence of games - that is, with an order - resulting in the given table. –  Ben Sep 24 '12 at 20:29
    
aryabhata: Thanks - yes, that would be a useful step. Unfortunately, it sounds rather hard... –  Ben Sep 24 '12 at 20:33
1  
a suggestion to study/solve this. specify it as a SAT problem. then try many random cases. see if any are hard for a standard solver. if not, maybe its a constrained subset in P. –  vzn Jun 24 '13 at 20:17

1 Answer 1

This is not a complete answer. I give a simpler statement of the problem and some remarks.

We start with a graph where vertices are labeled with $[n]$.

We have an operation that adds a directed edge from $v$ to $u$ to the graph, and if $label(v)<label(u)$ switches their labels.

Given a directed multi-graph $G$ with $n$ vertices and $e$ edges, check if it can be obtained using using the operation above.

It is easy to see that the problem is in $\mathsf{NP}$: a certificate is a (polynomial size) sequence of operations resulting in the $G$.

Observation

It seems that we can assume without loss of generality that all edges to the last vertex are added at the end of the sequence and all edges from it are added at the start of the sequence. This can be generalized to other vertices. Assume that we have remove all vertices with labels larger than $label(v)$. All edges to $v$ are added at the end of the sequence and all edges from $v$ are added at the start of the sequence.

I think it should be possible to combined this observation with Havel-Hakimi to give a polynomial time algorithm.

share|improve this answer
    
Hi. Thank you. Would you mind stating your observation again phrased in the context of ladders? I think there's a counterexample for a graph of order 3, but perhaps I misread. –  Ben Jul 20 '13 at 11:21
    
@Ben, I think it would be the following: you can assume that the last person on the ladder played all of the games that he won at the start of the tournament and played all of the games that he lost at the end of the tournament. Let me know if there is a counter-example to this, I haven't checked this carefully. –  Kaveh Jul 20 '13 at 13:09
    
Unfortunately, there are ladders like this one: A 2/2 B 0/1 C 0/1 –  Ben Jul 20 '13 at 14:29
    
@Ben, I think the example is consistent with what I wrote, i.e. it is not a counter-example to the observation. –  Kaveh Jul 22 '13 at 8:47
    
The ladder is valid. Let's assume that the last game played was a loss for C. Then prior to the last game, the ladder must have looked like this: C 0/0 B 0/1 A 1/1, but this ladder is invalid. Hence, we can't assume the last game was a loss for C. –  Ben Jul 22 '13 at 10:29

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.