 | ||
In graph theory, a cop-win graph is an undirected graph on which the pursuer (cop) 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 (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.
Contents
Pursuit-evasion
Cop-win graphs (and the complementary class of graphs, robber-win graphs) were introduced by Nowakowski & Winkler (1983) 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 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 v 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. 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.
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 two adjacent vertices of G either to the same vertex as each other or to a pair of adjacent vertices in H. Then, as they argue, the family of cop-win graphs is closed under retraction. For, 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.
Equivalence of cop-win and dismantlability
Every dismantlable graph is cop-win. A winning strategy for the cop is to find a dominated vertex v, and to follow (by induction) an optimal strategy on the graph formed by removing v, pretending that the robber is on the vertex that dominates v whenever he is actually on v. This 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. This strategy can be used as the basis for a proof by induction of the fact 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, 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 (as other dominated vertices are removed) 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:
In a graph with n vertices, m edges, and degeneracy d, this process can be carried out in time O(dm).
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. It constructs and maintains the actual deficit set (neighbors of x that are not neighbors of y) 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 log2 n vertices. It performs the following steps:
The time for this procedure is O(n2 + mn/log n).
Related families of graphs
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 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 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 hereditarily cop-win graphs are the graphs in which every induced subgraph is cop-win. This is not true for all cop-win graphs; for instance, the wheel graphs are cop-win but contain induced cycles of length more than four, which are not 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-wheel nor 5-wheel 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.