At my local squash club, there is a ladder which works as follows.
- At the beginning of the season we construct a table with the name of each
member of the club on a separate line.
- 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:
The order of the names doesn’t matter, since we have forgotten the original starting order.
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.)
- 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?
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 NP:
a certificate is a (polynomial size) sequence of operations resulting in the G.
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.