Cop-win graph

From Wikipedia, the free encyclopedia

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 chose to move along an edge of a graph or stay put, until the cop lands on the robber's vertex.[1] 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 (and the complementary class of graphs, robber-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 graph, chosen first by the cop and then by the robber. 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 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, no matter where the two players start, the cop can always force a win.[2]

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 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.[3] Nowakowski & Winkler (1983) call a vertex that is dominated by another vertex an irreducible vertex.[2]

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.[2][3]

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.[2][4] A cop following this inductive strategy 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.[5][6][7]

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.[2][8] 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 and never get caught. For a robber that behaves in this way, the removal of does not disadvantage the cop, because moving to the vertex that dominates is always at least as good of a choice. It follows by induction from these two principles that every finite cop-win graph is dismantlable.[2][9]

Closure properties[]

abcdefgh
8
Chessboard480.svg
h8 black king
a1 white king
8
77
66
55
44
33
22
11
abcdefgh
The white king (cop) can beat the black king (robber) on a chessboard, so the king's graph is a cop-win graph.

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.[2][10] 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 column of the black king while in each step remaining on the same row as the black king.[11]

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.[2]

Recognition algorithms[]

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).[12]

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:

  • 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 O(n/log n) per pair.
  • Repeat the following steps n/log n times, 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, using the initial set of decision trees, in time O(n/log n) per pair.
    • Repeat the following steps log n times:
      • Find a pair (x, y) with constructed but empty deficit set.
      • Delete vertex x
      • Remove x from all constructed deficit sets that it belongs to.
    • Build a decision tree for the log n 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.

The time for this procedure is O(n2 + mn/log n).[13]

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.[14][15] 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.[16]

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.[17]

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 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.[18] 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.[19]

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.[20] 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.[21]

History[]

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

References[]

  1. ^ Bonato, Anthony; Nowakowski, Richard J. (2011), The Game of Cops and Robbers on Graphs, Student Mathematical Library, 61, Providence, RI: American Mathematical Society, doi:10.1090/stml/061, ISBN 978-0-8218-5347-4, MR 2830217
  2. ^ Jump up to: a b c d e f g h i Nowakowski, Richard; Winkler, Peter (1983), "Vertex-to-vertex pursuit in a graph", Discrete Mathematics, 43 (2–3): 235–239, doi:10.1016/0012-365X(83)90160-7, MR 0685631
  3. ^ Jump up to: a b Chepoi, Victor (1998), "On distance-preserving and domination elimination orderings", SIAM Journal on Discrete Mathematics, 11 (3): 414–436, doi:10.1137/S0895480195291230, MR 1628110
  4. ^ Bonato & Nowakowski (2011), Theorem 2.3, page 32.
  5. ^ Bonato, A.; Golovach, P.; Hahn, G.; Kratochvíl, J. (2009), "The capture time of a graph", Discrete Mathematics, 309 (18): 5588–5595, doi:10.1016/j.disc.2008.04.004, MR 2567962
  6. ^ Gavenčiak, Tomáš (2010), "Cop-win graphs with maximum capture-time", Discrete Mathematics, 310 (10–11): 1557–1563, doi:10.1016/j.disc.2010.01.015, MR 2601265
  7. ^ Bonato & Nowakowski (2011), p. 36.
  8. ^ Bonato & Nowakowski (2011), Lemma 2.1, page 31.
  9. ^ Bonato & Nowakowski (2011), Theorem 2.2, page 32.
  10. ^ Bonato & Nowakowski (2011), Theorem 2.8, page 43.
  11. ^ For the fact that a strong product of paths is cop-win, see Nowakowski & Winkler (1983). For the fact that the king's graph is a strong product of paths, see Berend, Daniel; Korach, Ephraim; Zucker, Shira (2005), "Two-anticoloring of planar and related graphs" (PDF), 2005 International Conference on Analysis of Algorithms, Discrete Mathematics & Theoretical Computer Science Proceedings, Nancy: Association for Discrete Mathematics & Theoretical Computer Science, pp. 335–341, MR 2193130
  12. ^ Lin, Min Chih; Soulignac, Francisco J.; Szwarcfiter, Jayme L. (2012), "Arboricity, h-index, and dynamic algorithms", Theoretical Computer Science, 426–427: 75–90, arXiv:1005.2211, doi:10.1016/j.tcs.2011.12.006, MR 2891574
  13. ^ Spinrad, Jeremy P. (2004), "Recognizing quasi-triangulated graphs", Discrete Applied Mathematics, 138 (1–2): 203–213, doi:10.1016/S0166-218X(03)00295-6, MR 2057611. Spinrad gives a simpler but less tight time analysis of O(n3/log n). The total time spent in the step that removes x from deficit sets is O(m log n), dominated by the other terms in the time bound.
  14. ^ Hahn, Geňa; Laviolette, François; Sauer, Norbert; Woodrow, Robert E. (2002), "On cop-win graphs", Discrete Mathematics, 258 (1–3): 27–41, doi:10.1016/S0012-365X(02)00260-1, MR 2002070
  15. ^ Bonato & Nowakowski (2011), Section 7.4, Infinite chordal graphs, pp. 178–182.
  16. ^ Bonato & Nowakowski (2011), Section 7.5, Vertex-transitive cop-win graphs, pp. 182–187.
  17. ^ Bonato, Anthony; Kemkes, Graeme; Prałat, Paweł (2012), "Almost all cop-win graphs contain a universal vertex", Discrete Mathematics, 312 (10): 1652–1657, doi:10.1016/j.disc.2012.02.018, MR 2901161
  18. ^ Anstee, R. P.; Farber, M. (1988), "On bridged graphs and cop-win graphs", Journal of Combinatorial Theory, Series B, 44 (1): 22–28, doi:10.1016/0095-8956(88)90093-7, MR 0923263
  19. ^ Chepoi, Victor (1997), "Bridged graphs are cop-win graphs: an algorithmic proof", Journal of Combinatorial Theory, Series B, 69 (1): 97–100, doi:10.1006/jctb.1996.1726, MR 1426753
  20. ^ Jump up to: a b Aigner, M.; Fromme, M. (1984), "A game of cops and robbers", Discrete Applied Mathematics, 8 (1): 1–11, doi:10.1016/0166-218X(84)90073-8, MR 0739593
  21. ^ Bonato & Nowakowski (2011), pp. 1–3.
  22. ^ Quilliot, A. (1978), Jeux et pointes fixes sur les graphes [Games and fixed points on graphs], Thèse de 3ème cycle (in French), Pierre and Marie Curie University, pp. 131–145, as cited by Bonato & Nowakowski (2011)
  23. ^ Jump up to: a b c Bonato & Nowakowski (2011), p. 4.

External links[]

Retrieved from ""