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 in which he chases a robber, the players alternately
moving along an edge of a graph or staying 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 were introduced by in the context of the following pursuit-evasion game, whose invention they credit to G. Gabor and A. Quilliot. Two players, a cop and a robber, are positioned at different initial vertices of a given graph. They play in turns; 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 his 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, no matter where the two players start, the cop can always force a win.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. A graph is dismantlable if and only if it has a dismantling order.
Closure properties
The family of cop-win graphs is closed under strong products of graphs. The cop can win in a strong product of cop-win graphs by playing to win one of the factors of the product, and after doing so playing in the remaining factors in the same way while continuing to stay on the same vertex as the robber in the already-won factor. For instance, the king's graph, a strong product of two path graphs, is cop-win. The factor strategy for the white king would be to first move to the same row as the black king, and then move towards the black king while remaining on the same row as the black king.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 two adjacent vertices of either to the same vertex as each other or to a pair of adjacent vertices in. Then, as they argue, the family of cop-win graphs is closed under retraction. For, 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.
Equivalence of cop-win and dismantlability
Every dismantlable graph is cop-win. A winning strategy for the cop is to find a dominated vertex, and to follow an optimal strategy on the graph formed by removing, pretending that the robber is on the vertex that dominates whenever he is actually on. This 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. This strategy can be used as the basis for a proof by induction of the fact 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, if the robber plays optimally to make the game last as long as possible and the last position of the game before the cop wins has the cop at vertex c and the robber at r, then r must be dominated by c, else the robber could prolong the game for at least one move. The function that maps r onto c and leaves every other vertex in place is a retraction, so the graph formed by removing the dominated vertex must remain cop-win. By induction, it follows that every cop-win graph is dismantlable. The same argument shows that, in a graph with no dominated vertices, the robber can never lose: there is always a move to a vertex that is not adjacent to the cop. In an arbitrary graph that is not cop-win, the robber can win by removing all dominated vertices and playing within the remaining subgraph, which must be non-empty else the graph would be dismantlable.
Recognition algorithms and the family of all dismantling orders
If a vertex in a cop-win graph is dominated, then it remains dominated until it is either removed itself or it becomes the final vertex of a dismantling order. Therefore, the collection of valid dismantling orders has the structure of an antimatroid, and a dismantling order can be found by a simple greedy algorithm that repeatedly finds and removes any dominated vertex. The process succeeds if and only if the graph is cop-win, so 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 to find each successive vertex to remove 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.
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. It constructs and maintains the actual deficit set only when the deficit is small. To speed up its computations, it uses decision trees that classify vertices according to their adjacencies with small blocks of vertices. It performs the following steps:
- Group the vertices into blocks, build a decision tree for each block, and classify all vertices by their sets of neighbors within each block.
- Use this classification to compute the deficits for all adjacent pairs of vertices, in time per pair.
- Repeat the following steps times, 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, using the initial set of decision trees, in time per pair.
- *Repeat the following steps times:
- **Find a pair with constructed but empty deficit set.
- **Delete vertex
- **Remove from all constructed deficit sets that it belongs to.
- *Build a decision tree for the removed vertices and classify all vertices by their neighbors in this set.
- *Use the decision tree to update the deficits for all edges in constant time per edge.
Related families of graphs
Every finite chordal graph is a dismantlable graph, and every elimination ordering of a chordal graph is a valid dismantling order. However, there exist infinite chordal graphs that are not cop-win.Every graph that has a universal vertex is dismantlable, for 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 -vertex dismantlable graphs, the fraction of these graphs that have a universal vertex goes to one in the limit as goes to infinity.
is cop-win but not hereditarily cop-win.
The hereditarily cop-win graphs are the graphs in which every isometric subgraph 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.