Using up the edges instead

A token on a graph found the sharpest contrast geography has to offer. With arrows on the edges, the game in which a token slides to a vertex not yet visited is complete for polynomial space. Take the arrows off and the same game is settled by a maximum matching: the first player wins from a vertex exactly when every maximum matching of the graph covers it. One word of the rules separates a search that nobody can shorten from a criterion a person can check on paper.

That essay ended by naming the other variant and declining to say anything about it. Geography has two things a move can use up. In the game measured there, the token may not return to a vertex it has visited. In the other, it may not cross an edge it has already crossed, and it may come back to a vertex as often as that vertex has unused edges. The board is the same, the token is the same, and a player with no legal move still loses.

The question is whether the matching survives the change, and the answer turns out to have an exact boundary.

A tree cannot tell the two rules apart #

Before any census, one case can be settled by argument, and it is the case that decides where to look. On a tree there is exactly one route between any two vertices. A token that could return to a vertex would have to arrive by a second route, which a tree does not have. So on a tree a trail never revisits a vertex, and forbidding repeated vertices and forbidding repeated edges forbid exactly the same moves: on a tree, vertex geography and edge geography are one game.

The tree drawn is the one the earlier essay used, and the table says so row by row. From b and d, the two branch points, the first player wins both games; from the four leaves the first player loses both. The matching criterion, which never looks at either game, names all six.

That argument is also a prediction about everywhere else. If the criterion is right about the edge game on trees only because the edge game is the vertex game there, then the first place it has any chance of failing is the first graph with a cycle.

The first cycle #

It does fail there, and completely. Take the triangle and start at a. In the vertex game the first player moves to b, the second moves to c, and the first player is stuck, since the only vertex left next to c is a, already used. The first player loses from every start, and the criterion agrees: the triangle’s maximum matchings are single edges, each of the three misses a vertex, and so no vertex is covered by all of them.

In the edge game the same three moves are made, and one more is available. From c the edge back to a has not been crossed. The first player takes it, arrives at a with both of a’s edges spent, and the second player is stuck. The first player wins from every start. The criterion has nothing to correct in its reasoning, since it never mentioned the history. The return along the third edge is simply a move it was never built to see.

That return is the whole mechanism of this essay in one move. A cycle is exactly what lets a trail come back to a vertex through an edge not yet used, and every disagreement found below is some version of it.

An even cycle reverses every start #

The triangle has an odd cycle, and a matching argument is famously sensitive to odd cycles — they are what blocks a perfect matching on three vertices. So the obvious hope is that even cycles, which behave well for matchings, might leave the criterion intact.

The four-cycle ends that hope in one drawing. It has two perfect matchings, every vertex is covered by both, and the vertex game is a first-player win from every start: from a, three moves to b, c and d, and the second player finds both of d’s neighbours used.

In the edge game the token goes round. From a to b to c to d, and then the fourth edge, d back to a, is still unused, so the second player crosses it. The first player is now at a with both edges spent. Every start of the four-cycle is a second-player win, and the criterion, reading a perfect matching, calls every one of them for the first player.

The two games have swapped at every vertex, and they have swapped because of the parity of the cycle’s length. Four edges round a four-cycle is an even number of moves, and it hands the last move to the second player. Three edges round a triangle is odd, and it hands it to the first. The matching criterion reads the parity of a matching; the edge game, on a cycle, is reading the parity of the cycle, and those are different parities.

The mistake in the other direction #

The triangle’s three mistakes all call a won start lost, and the four-cycle’s four all call a lost start won. Neither is a graph on which the criterion is right at some starts and wrong at others, and the smallest such graph is the triangle with a tail: four vertices and four edges, since the only other connected graph of that size with a cycle is the four-cycle itself.

From the triangle’s three vertices the criterion is right about the edge game, and from the pendant vertex d it is wrong. The graph has exactly one maximum matching, ad together with bc, and it covers every vertex, so the vertex game is a first-player win from every start, d included: the first player moves along the matched edge each time and the second player runs out first. In the edge game the first player’s only move from d is to a, and that spends a’s pendant edge. The play then goes round the triangle — a to b, b to c, c back to a, three moves shared between the players — and arrives at a with every one of its edges crossed and the first player to move. A start the matching calls won is lost, and again the losing line is a trail returning along a cycle.

Every graph on six vertices or fewer #

Four drawings show where the criterion can fail. They do not show how often, and a single graph is always open to the objection that it was chosen for being awkward. So the question is put to every connected graph on up to six vertices: 143 of them, one of each shape, from every one of their 810 starting vertices.

For each start, three things are computed separately. The vertex game is solved by exhaustive search, the criterion is computed from maximum matchings, and the edge game is solved by its own exhaustive search. The first two must agree everywhere, since that is the theorem, and they do. The first and the third must agree on every tree, since there they are one game, and they do.

The rest is measurement. On the fourteen trees the criterion is right at all sixty-five starts. On the 129 graphs with at least one cycle it is right at 480 of 745 starts, 64 per cent. The share hovers between 57 and 68 per cent across every number of cycles from one to nine, which means the criterion is not degrading gracefully as cycles are added. It stops being a criterion at the first cycle and becomes something close to a biased coin.

Close to, not quite. The direction of the misses is not symmetric, and it moves with the cycles. With one cycle the criterion calls a lost start won 21 times and a won start lost 16 times. With four cycles it is 49 against 5. With four cycles or more, 116 of its 129 misses call a win that is really a loss. From seven cycles on there are no misses the other way at all.

That lean has a reason visible in the two games separately. As cycles are added the vertex game’s first player wins more and more often: from 34 of 65 starts on trees, to 126 of 156 with three cycles, to every one of the thirty starts with seven. The edge game does not follow. Its first player wins from between about half and two thirds of the starts at every number of cycles, and every extra edge is also another route by which a trail can come back. So on a dense graph the matching nearly always covers the start and says first player, and the edge game agrees only about three times in five.

The last row is a single graph, the complete graph on six vertices, and the criterion is right at all six of its starts. That is not a recovery. Every vertex of the complete graph is covered by every perfect matching, so the criterion says first player everywhere, and the edge game happens to be a first-player win from every start as well. One graph agreeing is exactly the kind of case a census exists to put in proportion.

Even cycles, odd cycles and two cheaper rules #

The four-cycle was one graph. Over all of them the conclusion holds and sharpens: on the fourteen graphs whose cycles are all even, the criterion is right at 45 of 80 starts, 56 per cent — worse than its 65 per cent on the 115 graphs with an odd cycle. Of its misses on the even-cycle graphs, thirty-three are wins called for a player who loses. A bipartite graph is the natural home of matching arguments, and in this game it is the place the matching argument does worst.

The two cheaper rules are there as a floor rather than as rivals. The first player wins when the start has odd degree is right at about half the starts with an odd cycle and at a third of the starts on trees. The first player wins when the graph has an odd number of edges does no better on graphs with an odd cycle. On the even-cycle graphs, though, both parity rules beat the matching criterion — 47 and 52 starts against 45 — which is less a compliment to parity than a measure of how little the matching still knows about this game.

How hard is it is careful about the difference between a measurement like this and a hardness result, and it applies here with full force. That no rule tried reads the edge game is evidence about three rules. The theorem that says no efficient rule is expected is a different kind of statement, and it is quoted in the section on names below rather than established.

What the larger history costs #

A token on a graph made the point that geography’s position is not a vertex but a vertex and a history. In the vertex game the history is a set of vertices, so a graph on n vertices has at most n · 2ⁿ states. In the edge game the history is a set of edges, and a graph on six vertices can have fifteen. The census makes the difference concrete. Over the 112 connected graphs on six vertices the vertex game’s search stores 19,220 states and the edge game’s 148,362. At five vertices the ratio is 3.1, at four 1.6, and it grows with every vertex because the number of possible edges grows as the square of the vertices.

That is also a reminder of what the matching buys in the vertex game. With the criterion in hand, none of those 19,220 states needs to be visited: two matching computations settle every start. The edge game’s 148,362 states are, as far as this census can show, the price of an answer, and nothing measured here reduces it. It is the same distinction a strategy is not a certificate draws between a short object that settles a game and a strategy that has to be searched out.

Edges used up elsewhere in these essays #

Geography is not the only game in which an edge, once used, is gone, and two others sit close enough to be worth naming.

In Dots and Boxes and its strings-and-coins form, a move cuts a string and the string does not come back, and the analysis of a board also turns on chains and loops — on whether a structure closes up on itself. There the loop’s extra behaviour is a matter of who is forced to open it; here a cycle’s extra behaviour is a trail’s ability to return along it. And in the Shannon switching game the players claim and delete links, and a criterion survives — two edge-disjoint spanning trees — because the game is about which links end up connected rather than about the order a single token uses them in.

The contrast with the switching game is instructive in the other direction. A structural criterion there, about trees inside the graph, decides a game on edges. A structural criterion here, about matchings, decides a game on vertices and fails on edges. What a criterion can capture depends on whether the game’s answer is a property of the final set of edges or of a route through them.

Names: who proved what #

Generalised geography was shown complete for polynomial space by Even and Tarjan in 1976, Schaefer carried the same treatment through a list of other games in 1978, and the reduction that makes it hard is drawn in these essays. The undirected versions are due to Fraenkel, Scheinerman and Ullman in 1993: they proved that undirected vertex geography is decided by the matching criterion used above, and that undirected edge geography, in contrast, remains complete for polynomial space. So the census’s conclusion — that the matching does not read the edge game — agrees with what is known, and the known result is the stronger one: no rule that runs in polynomial time is expected to read it unless polynomial time and polynomial space coincide.

The census adds something the theorem does not state: where the criterion fails first, which way it leans, and that the graphs most friendly to matchings are among the worst for it.

What the census cannot show #

Six vertices is small. The graphs are every connected graph up to that size, so nothing in range was skipped, but a trend in the shares from one cycle to nine is drawn from very few graphs at the high end — two graphs with eight cycles, one with nine. The direction of the lean is the robust part; the exact shares are not.

Only three rules are tried. The criterion is the natural one to transplant and the two parity rules are floors. A cleverer rule, reading cycles as well as matchings, might do far better on graphs this small; the hardness result says no such rule stays efficient on every graph, and says nothing about how well one might do on these.

Every start is weighted equally. A vertex of degree one on a dense graph counts as much as a vertex in its middle, and the shares would move under any other weighting.

The rules the counts assume #

A token sits on a vertex of an undirected graph. In vertex geography a move slides it along an edge to a vertex not yet visited, the starting vertex counting as visited. In edge geography a move slides it along an edge not yet crossed to that edge’s other end, and vertices may be revisited. In both, the player to move with no legal move loses — normal play. A graph is connected and simple: no loops, no repeated edges. The matching criterion says the first player wins from a vertex exactly when every maximum matching of the graph covers it, computed as whether deleting the vertex shrinks the largest matching.

Still open: a criterion that reads cycles #

The failures all have one shape: a trail that returns along a cycle to a vertex with its edges spent. That suggests a repair of a specific kind — a rule that reads the matching and the lengths of the cycles through the start, much as the four-cycle’s reversal is a matter of an even length and the triangle’s of an odd one. Whether a rule of that kind names the winner on every unicyclic graph, where there is exactly one cycle to read, is a finite question with a census of twenty-one graphs and 114 starts behind it, and it is the next thing to measure.