Cop-win graph
In graph theory, a cop-win graph is an undirected graph on which the pursuer 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 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
The closed neighborhood of a vertex in a given graph is the set of vertices consisting of itself and all other vertices adjacent to. The vertex is said to be dominated by another vertex when. That is, and are adjacent, and every other neighbor of is also a neighbor of. 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 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 as a base case. For a larger graph, let be any dominated vertex. By the induction hypothesis, the cop has a winning strategy on the graph formed by removing, and can follow the same strategy on the original graph by pretending that the robber is on the vertex that dominates whenever the robber is actually on. Following this strategy will result either in an actual win of the game, or in a position where the robber is on 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 vertices takes at most 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 -vertex graph, the cop can force a win in at most 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 is a dominated vertex in a cop-win graph, then removing 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 whenever the cop is actually on, and never get caught. It follows by induction from these two principles that every finite cop-win graph is dismantlable.
Closure properties
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.
define a retraction of a graph onto one of its induced subgraphs to be a mapping from the vertices of to the vertices of that maps each vertex of to itself, and that maps each pair of adjacent vertices of either to the same vertex as each other or to a pair of adjacent vertices in. Then the family of cop-win graphs is closed under retraction. This is because a cop can win in by simulating a game in. Whenever the winning strategy in would call for the cop to stay put, or to follow an edge whose endpoints are mapped to the same vertex of, the cop stays put in. And in all other cases, the cop follows the edge in that is the image under the retraction of a winning edge in.
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 that is an endpoint of an edge participating in a number of triangles equal to the degree of minus one, delete, and decrement the triangles per edge of each remaining edge that formed a triangle with.
Counting neighbors
An alternative and more complicated algorithm by involves maintaining a number called the deficit for each adjacent pair of vertices, which counts the number of neighbors of that are not neighbors of. If this number becomes zero, after other vertices have been removed, then is dominated by and may also be removed. It constructs and maintains the actual deficit set only for pairs for which the deficit is small.To speed up its computations, Spinrad's algorithm uses a subroutine for counting neighbors among small blocks of vertices. If 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 can be represented as a binary number with bits. These numbers allow the algorithm to count, for any two vertices and, how much contributes to the deficit of and, 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 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 times:
- **Find a pair 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
- **Remove from all constructed deficit sets that it belongs to.
- *Construct a block of the 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.