Cop-win graph

In graph theory, a cop-win graph is an undirected graph on which the pursuer (cop) can always win a pursuit–evasion game against a robber, with the players taking alternating turns in which they can choose to move along an edge of a graph or stay put, until the cop lands on the robber's vertex. Finite cop-win graphs are also called dismantlable graphs or constructible graphs, because they can be dismantled by repeatedly removing a dominated vertex (one whose closed neighborhood is a subset of another vertex's neighborhood) or constructed by repeatedly adding such a vertex. The cop-win graphs can be recognized in polynomial time by a greedy algorithm that constructs a dismantling order. They include the chordal graphs, and the graphs that contain a universal vertex.

Definitions

Pursuit–evasion

Cop-win graphs can be defined by a pursuit–evasion game in which two players, a cop and a robber, are positioned at different initial vertices of a given undirected graph. The cop chooses an initial vertex first, and then the robber chooses. Next, they play in turns, again with the cop first. On each player's turn, the player may either move to an adjacent vertex or stay put. The game ends, and the cop wins, if the cop can end a turn on the same vertex as the robber. The robber wins by indefinitely evading the cop. A cop-win graph is a graph with the property that, when the players choose starting positions and then move in this way, the cop can always force a win. If an undirected graph is not a cop-win graph, it is called a robber-win graph.

Dismantling

In this graph, vertex v is dominated by vertex w: the closed neighborhood of v, N[v] (inner shaded region) is a subset of the closed neighborhood of w, N[w] (outer shaded region)

The closed neighborhood N[v] of a vertex v in a given graph is the set of vertices consisting of v itself and all other vertices adjacent to v. The vertex v is said to be dominated by another vertex w when N[v] ⊂ N[w]. That is, v and w are adjacent, and every other neighbor of v is also a neighbor of w. Nowakowski & Winkler (1983) call a vertex that is dominated by another vertex an irreducible vertex.

A dismantling order or domination elimination ordering of a given graph is an ordering of the vertices such that, if the vertices are removed one-by-one in this order, each vertex (except the last) is dominated at the time it is removed. A graph is dismantlable if and only if it has a dismantling order.

Equivalence of cop-win and dismantlability

Every finite dismantlable graph is cop-win. This can be proved by mathematical induction, with a one-vertex graph (trivially won by the cop) as a base case. For a larger graph, let v be any dominated vertex. By the induction hypothesis, the cop has a winning strategy on the graph formed by removing v, and can follow the same strategy on the original graph by pretending that the robber is on the vertex that dominates v whenever the robber is actually on v. Following this strategy will result either in an actual win of the game, or in a position where the robber is on v and the cop is on the dominating vertex, from which the cop can win in one more move. A cop following this inductive strategy on a graph with n vertices takes at most n moves to win, regardless of starting position. By choosing the cop's starting position carefully, one can use the same idea to prove that, in an n-vertex graph, the cop can force a win in at most n − 4 moves.

Conversely, every cop-win graph has a dominated vertex. For, in a graph with no dominated vertices, if the robber has not already lost, then there is a safe move to a position not adjacent to the cop, and the robber can continue the game indefinitely by playing one of these safe moves at each turn. Additionally, if v is a dominated vertex in a cop-win graph, then removing v must produce another cop-win graph, for otherwise the robber could play within that subgraph, pretending that the cop is on the vertex that dominates v whenever the cop is actually on v, and never get caught. It follows by induction from these two principles that every finite cop-win graph is dismantlable.

Closure properties

	a	b	c	d	e	f	g	h
8									8
7									7
6									6
5									5
4									4
3									3
2									2
1									1
	a	b	c	d	e	f	g	h

One of the two kings, playing as cop, can beat the other king, playing as robber, on a chessboard, so the king's graph is a cop-win graph.

A family of mathematical objects is said to be closed under a set of operations if combining members of the family always produces another member of that family. In that sense, the family of cop-win graphs is closed under strong products of graphs. Each vertex in the strong product corresponds to a pair of vertices in each of two factor graphs. The cop can win in a strong product of two cop-win graphs by, first, playing to win in one of these two factor graphs, reaching a pair whose first component is the same as the robber. Then, while staying in pairs whose first component is the same as the robber, the cop can play to win in the second of the two factors. For instance, the king's graph, a strong product of two path graphs, is cop-win. On this graph, the vertices correspond to the squares of a chessboard, and both the cop and robber move like a king in the game of chess, to a square that is adjacent horizontally, vertically, or diagonally. The product-based strategy for the cop would be to first move to the same row as the robber, and then move towards the column of the robber while in each step remaining on the same row as the robber.

It is not true that every induced subgraph of a cop-win graph is cop-win. However, certain special induced subgraphs do remain cop-win. Nowakowski & Winkler (1983) define a retraction of a graph G onto one of its induced subgraphs H to be a mapping from the vertices of G to the vertices of H that maps each vertex of H to itself, and that maps each pair of adjacent vertices of G either to the same vertex as each other or to a pair of adjacent vertices in H. Then the family of cop-win graphs is closed under retraction. This is because a cop can win in H by simulating a game in G. Whenever the winning strategy in G would call for the cop to stay put, or to follow an edge whose endpoints are mapped to the same vertex of H, the cop stays put in H. And in all other cases, the cop follows the edge in H that is the image under the retraction of a winning edge in G.

Recognition algorithms

Several different strategies are known for checking whether a graph is cop-win, and if so finding a dismantling sequence allowing the cop to win in the graph. These include greedy algorithms, and a more complicated algorithm based on counting shared neighbors of vertices.

Greedy algorithm

A dismantling order can be found by a simple greedy algorithm that repeatedly finds and removes any dominated vertex. The process succeeds, by reducing the graph to a single vertex, if and only if the graph is cop-win. Therefore, as well as providing an algorithm for finding dismantling orders, this method provides an algorithm for testing whether a given graph is cop-win. One way for this algorithm to find the dominated vertices that it removes is to perform the following steps:

• Find all triangles in the graph, and count the number of triangles that each edge participates in.
• Repeatedly find a vertex v that is an endpoint of an edge participating in a number of triangles equal to the degree of v minus one, delete v, and decrement the triangles per edge of each remaining edge that formed a triangle with v.

In a graph with n vertices, m edges, and degeneracy d, this process can be carried out in time O(dm).

Counting neighbors

An alternative and more complicated algorithm by Spinrad (2004) involves maintaining a number called the deficit for each adjacent pair of vertices (x, y), which counts the number of neighbors of x that are not neighbors of y. If this number becomes zero, after other vertices have been removed, then x is dominated by y and may also be removed. It constructs and maintains the actual deficit set (neighbors of x that are not neighbors of y) only for pairs (x, y) for which the deficit is small.

To speed up its computations, Spinrad's algorithm uses a subroutine for counting neighbors among small blocks of log₂ n vertices. If B is a set of vertices that the algorithm has selected to be a block, then for any other vertex, the set of neighbors of that vertex in B can be represented as a binary number with log₂ n bits. These numbers allow the algorithm to count, for any two vertices x and y, how much B contributes to the deficit of x and y, in constant time, by a combination of bitwise operations and table lookups. Using this subroutine, the algorithm performs the following steps:

• Create blocks from an arbitrary partition of the vertices, and find the numbers representing the neighbors of each vertex in each block.
• Use the block-counting subroutine to compute the deficit for all adjacent pairs of vertices.
• Repeat the following steps until all vertices have been removed:
  • Construct the deficit set for all adjacent pairs that have deficit at most log n and that have not already had this set constructed. The initial system of blocks can be used to speed up this construction.
  • Repeat the following steps log n times:
    • Find a pair (x, y) with constructed but empty deficit set. If no such pair exists, the graph is not cop-win; in this case, abort the algorithm.
    • Delete vertex x
    • Remove x from all constructed deficit sets that it belongs to.
  • Construct a block of the log n removed vertices and numbers representing all other vertices' adjacencies within this block.
  • Use the block-counting subroutine, on this one block, to update the deficits for all edges.

Spinrad states the total time for this algorithm as O(n³/log n).

In infinite graphs

The computability of algorithmic problems involving cop-win graphs has also been studied for infinite graphs. In the case of infinite graphs, it is possible to construct computable countably infinite graphs, on which an omniscient robber could always evade any cop, but for which no algorithm can follow this strategy. These graphs can even be infinite trees, with a finite number of edges per vertex. By Kőnig's lemma, such a tree must have an infinite path, and an omniscient robber can win by walking away from the cop along this path, but the path cannot be found by an algorithm. Instead, every algorithm for choosing moves for the robber can be beaten by a cop who simply walks in the tree along the unique path towards the robber. Analogously, it is possible to construct computable countably infinite cop-win graphs, on which an omniscient cop has a winning strategy that always terminates in a finite number of moves, but for which no algorithm can follow this strategy. On such graphs, every algorithm for choosing moves for the cop can be evaded indefinitely by the robber.

Related families of graphs

In this graph, u is a universal vertex: it is adjacent to all other vertices

Every finite chordal graph is a dismantlable graph, and every elimination ordering of a chordal graph (an ordering of the vertices in which the later neighbors of each vertex form a clique) is a valid dismantling order. However, there exist infinite chordal graphs, and even infinite chordal graphs of diameter two, that are not cop-win. For other types of graphs, there may exist infinite cop-win graphs of that type even when there are no finite ones; for instance, this is true for the vertex-transitive graphs that are not complete graphs.

A universal vertex in a graph is a vertex u that is adjacent to all other vertices. Whenever a graph has a universal vertex, it is dismantlable, because every other vertex is dominated by the universal vertex, and any vertex ordering that places the universal vertex last is a valid dismantling order. Conversely, almost all dismantlable graphs have a universal vertex, in the sense that, among all n-vertex dismantlable graphs, the fraction of these graphs that have a universal vertex goes to one in the limit as n goes to infinity.

The visibility graphs of simple polygons are always cop-win. These are graphs defined from the vertices of a polygon, with an edge whenever two vertices can be connected by a line segment that does not pass outside the polygon. (In particular, vertices that are adjacent in the polygon are also adjacent in the graph.) Even when the cop and robber are allowed to move on straight line segments within the polygon, rather than vertex-to-vertex, the cop can win by always moving on the first step of a shortest path to the robber. Such a move cuts off part of the polygon which the robber can never double back to reach. When the cop starts at a vertex and the robber is restricted to moves between vertices, this strategy also limits the cop to vertices, so it is a valid winning strategy for the visibility graph.

The five-vertex wheel graph is cop-win but not hereditarily cop-win.

The hereditarily cop-win graphs are the graphs in which every isometric subgraph (a subgraph $H\subseteq G$ such that for any two vertices in $H$ the distance between them measured in $G$ is the same as the distance between them measured in $H$) is cop-win. This is not true for all cop-win graphs; for instance, the five-vertex wheel graph is cop-win but contains an isometric 4-cycle, which is not cop-win, so this wheel graph is not hereditarily cop-win. The hereditarily cop-win graphs are the same as the bridged graphs, graphs in which every cycle of length four or more has a shortcut, a pair of vertices closer in the graph than they are in the cycle. A cop-win graph is hereditarily cop-win if and only if it has neither the 4-cycle nor 5-cycle as induced cycles. For a hereditarily cop-win graph, the reversal of any breadth-first traversal is a valid dismantling order, from which it follows that any vertex can be chosen as the last vertex of a dismantling order.

A similar game with larger numbers of cops can be used to define the cop number of a graph, the smallest number of cops needed to win the game. The cop-win graphs are exactly the graphs of cop number equal to one. Bonato and Nowakowski describe this game intuitively as the number of ghosts that would be needed to force a Pac-Man player to lose, using the given graph as the field of play. The game used to define cop number should be distinguished from a different cops-and-robbers game used in one definition of treewidth, which allows the cops to move to arbitrary vertices rather than requiring them to travel along graph edges.

History

The game with a single cop, and the cop-win graphs defined from it, were introduced by Quilliot (1978). Another early reference is the work of Nowakowski & Winkler (1983), who were introduced to the game by G. Gabor. The game with multiple cops, and the cop number defined from it, were first studied by Aigner & Fromme (1984).

External links

• Dismantlable graphs, Information System on Graph Classes and their Inclusions