vi. Games on Graphs and Matchings

Games played by moving a token or pieces on a graph. Some are solved by matching theory or a structural characterization in polynomial time; close relatives are PSPACE-complete.

Game	Rule	Answer	Complexity
undirected vertex geography	a token starts on $s$ (visited); players alternately move it to an unvisited neighbour; who cannot move loses	the first player wins iff every maximum matching covers $s$ ($s\notin D$ in Gallai–Edmonds)	$O(V^3)$
undirected edge geography	the same, but edges may not be reused	PSPACE-complete (Fraenkel, Scheinerman and Ullman, 1993)
directed vertex / edge geography	on a digraph	PSPACE-complete (Schaefer 1978; Lichtenstein and Sipser 1980 for planar)
tokens moving on a DAG, sum of several tokens	move one token along an arc	XOR of Grundy values of the token positions	$O(V+E)$: Sprague–Grundy
tokens on a graph with cycles		generalized Sprague–Grundy / retrograde	Loopy Games
cops and robber (one cop, both may stay; the cop wins by landing on the robber)		the cop wins iff the graph is dismantlable (Nowakowski–Winkler, Quilliot, 1983)	$O(V^3)$
Shannon switching game (Short claims edges to connect $u,v$; Cut deletes edges)		Short, moving second, wins iff some subgraph containing $u,v$ has two edge-disjoint spanning trees (Lehman, 1964)	matroid union: Matroid Intersection
Hex, Chomp		strategy stealing	Chomp and Hex

Undirected vertex geography

The Gallai–Edmonds decomposition splits the vertices into $D$ (missed by some maximum matching), $A=N(D)\setminus D$ and $C$ (the rest); Blossom and gallaiEdmonds are in General Matching, with their proofs.

// Uses Blossom and gallaiEdmonds from the General Matching note. Token on s, s already visited.
bool geographyFirstWins(int n, const vector<pair<int, int>>& edges, int s) {
    Blossom B(n);
    for (auto [u, v] : edges) B.addEdge(u, v);
    B.run();
    return gallaiEdmonds(B)[s] != 0;                     // first player wins iff s is covered by every maximum matching
}

Proof: the first player wins iff every maximum matching covers s

If every maximum matching covers $s$: fix a maximum matching $M$. The first player always moves along $M$: first to $M(s)$, and after the opponent moves to $v$, to $M(v)$. This is always possible. $M(v)$ is unvisited, because visited vertices come in $M$-pairs (each first-player move completes a pair) and $v$ itself was unvisited. And $v$ is matched: otherwise the path $s,M(s),\dots ,v$ played so far alternates, starting with a matched edge at $s$ and ending at the unmatched $v$, and flipping it gives a maximum matching that misses $s$. So the first player always has a move and wins (the game is finite).

If some maximum matching $M$ misses $s$: the second player answers every move to $v$ with $M(v)$. Each $v$ the first player reaches is matched, otherwise the play $s,v_1,M(v_1),\dots ,v$ would be an $M$-augmenting path ($s$ and $v$ both free), contradicting maximality; and $M(v)$ is unvisited by the same pairing argument. So the second player always has a move and wins. Hence the first player wins iff $s\notin D$. Checked against exhaustive game search on random graphs with up to 10 vertices.

Cops and robber

The cop chooses a start vertex, then the robber; then they alternate, the cop first, each moving along an edge or staying put. The cop wins by occupying the robber’s vertex. A vertex $r$ is a corner if some $w\ne r$ has $N[r]\subseteq N[w]$ (closed neighbourhoods); a graph is dismantlable if corners can be deleted one by one down to a single vertex.

bool copWin(const vector<vector<int>>& adj) {               // connected graph; greedy dismantling, O(n^3) bitsets
    int n = sz(adj); vector<bitset<512>> N(n); vector<char> alive(n, 1);
    for (int v = 0; v < n; v++) { N[v][v] = 1; for (int u : adj[v]) N[v][u] = 1; }
    for (int left = n; left > 1; left--) {
        int corner = -1;
        for (int r = 0; r < n && corner < 0; r++) if (alive[r])
            for (int w = 0; w < n; w++) if (w != r && alive[w] && (N[r] & ~N[w]).none()) { corner = r; break; }
        if (corner < 0) return false;
        alive[corner] = 0;
        for (int v = 0; v < n; v++) N[v][corner] = 0;
    }
    return true;
}

Proof: cop-win iff dismantlable, and the greedy order does not matter

Retractions. If $r$ is a corner dominated by $w$, the map $f$ fixing every vertex except $f(r)=w$ sends edges to edges or to a single vertex ($y\in N[r]\subseteq N[w]$), so a legal move in $G$ maps to a legal move (or a stay) in $G-r$.

Dismantlable $\Rightarrow$ cop-win. Induction on $n$. Delete the first corner $r$; $G-r$ is cop-win. The cop plays the winning strategy of $G-r$ against the shadow $f(\text{robber})$, whose moves are legal in $G-r$; eventually the cop stands on the shadow. If the robber is not on $r$, it is caught. If it is on $r$, the cop is on $w$, and every robber move stays in $N[r]\subseteq N[w]$: the cop catches it next turn.

Cop-win $\Rightarrow$ a corner exists, and deleting any corner keeps the graph cop-win. If some vertex $c$ is adjacent to all others, every other vertex is a corner. Otherwise let the robber delay capture as long as possible; consider its last move, from $r$ with the cop on $c\ne r$: every robber option (all of $N[r]$) lies in $N[c]$, since the cop captures next turn, so $r$ is a corner. For any corner $r$ of a cop-win $G$, $G-r$ is cop-win: the cop plays the $G$-strategy (against a robber who never uses $r$) but stands on $f(\text{cop position})$; when the $G$-cop lands on the robber at $x\ne r$, the image is $x$ too. Hence a cop-win graph is dismantled by deleting corners in any order, which is why the greedy loop is correct, and a graph where the loop gets stuck is robber-win. Checked against retrograde analysis of the game (states: cop, robber, player to move) on random connected graphs with up to 7 vertices.

Related notes

• General Matching (Blossom, Gallai–Edmonds)
• Loopy Games (retrograde analysis)
• Complexity Theory (PSPACE-completeness of games)