28
$\begingroup$

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?

Improve this question
$\endgroup$
9
  • 2
    $\begingroup$ Perhaps there is a Havel Hakimi type theorem for directed multigraphs... $\endgroup$
    – Aryabhata
    Sep 20, 2012 at 3:27
  • $\begingroup$ 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? $\endgroup$
    – utdiscant
    Sep 24, 2012 at 4:53
  • $\begingroup$ 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. $\endgroup$
    – Ben
    Sep 24, 2012 at 20:29
  • $\begingroup$ aryabhata: Thanks - yes, that would be a useful step. Unfortunately, it sounds rather hard... $\endgroup$
    – Ben
    Sep 24, 2012 at 20:33
  • 1
    $\begingroup$ 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. $\endgroup$
    – vzn
    Jun 24, 2013 at 20:17

2 Answers 2

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$
7
  • $\begingroup$ 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. $\endgroup$
    – Ben
    Jul 20, 2013 at 11:21
  • $\begingroup$ @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. $\endgroup$
    – Kaveh
    Jul 20, 2013 at 13:09
  • $\begingroup$ Unfortunately, there are ladders like this one: A 2/2 B 0/1 C 0/1 $\endgroup$
    – Ben
    Jul 20, 2013 at 14:29
  • $\begingroup$ @Ben, I think the example is consistent with what I wrote, i.e. it is not a counter-example to the observation. $\endgroup$
    – Kaveh
    Jul 22, 2013 at 8:47
  • $\begingroup$ 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. $\endgroup$
    – Ben
    Jul 22, 2013 at 10:29
0
$\begingroup$

I haven't solved the problem, but I have partial results, the statements of which are given below. I'll write up the proofs if anyone's interested.

Proposition. Suppose that the ladder (1) contains more than one player (2) contains an equal number of wins and losses; and (3) is such that each player has won at least one game and lost at least one game. Then the ladder is valid.

Let $W_i$ be the number of wins of player $i$, $L_i$ the number of losses of player $i$ and $R_i$ the rank (where higher is better).

Proposition (due to Fabio Parisi). If $L_i=0$ and the ladder is valid, then $$W_i \le \sum_{k:R_k > R_i, W_k > 0} (L_k - 1)^+ + \sum_{k:R_k<R_i}L_k,$$ and a corresponding bound holds for $L_i$ in the case that $W_i=0$.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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