graph theory In mathematics, graph theory is the study of ''graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conne ...

, 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. 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 In computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by ...

by a greedy algorithm that constructs a dismantling order. They include the

chordal graph In the mathematical area of graph theory, a chordal graph is one in which all cycles of four or more vertices have a ''chord'', which is an edge that is not part of the cycle but connects two vertices of the cycle. Equivalently, every induced cy ...

s, and the graphs that contain a

universal vertex In graph theory, a universal vertex is a vertex of an undirected graph that is adjacent to all other vertices of the graph. It may also be called a dominating vertex, as it forms a one-element dominating set in the graph. (It is not to be confused ...

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 (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 Mathematical induction is a method for proving that a statement ''P''(''n'') is true for every natural number ''n'', that is, that the infinitely many cases ''P''(0), ''P''(1), ''P''(2), ''P''(3), ... all hold. Informal metaphors help ...

, with a one-vertex graph (trivially won by the cop) 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 Closed may refer to: Mathematics * Closure (mathematics), a set, along with operations, for which applying those operations on members always results in a member of the set * Closed set, a set which contains all its limit points * Closed interval, ...

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 In graph theory, a king's graph is a graph that represents all legal moves of the king chess piece on a chessboard where each vertex represents a square on a chessboard and each edge is a legal move. More specifically, an n \times m 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 Chess is a board game for two players, called White and Black, each controlling an army of chess pieces in their color, with the objective to checkmate the opponent's king. It is sometimes called international chess or Western chess to disti ...

, 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 Degree may refer to: As a unit of measurement * Degree (angle), a unit of angle measurement ** Degree of geographical latitude ** Degree of geographical longitude * Degree symbol (°), a notation used in science, engineering, and mathematics ...

of minus one, delete , and decrement the triangles per edge of each remaining edge that formed a triangle with . In a graph with vertices, edges, and

degeneracy Degeneracy, degenerate, or degeneration may refer to: Arts and entertainment * ''Degenerate'' (album), a 2010 album by the British band Trigger the Bloodshed * Degenerate art, a term adopted in the 1920s by the Nazi Party in Germany to descri ...

, this process can be carried out in time .

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'' (neighbors of that are not neighbors of ) 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 A binary number is a number expressed in the base-2 numeral system or binary numeral system, a method of mathematical expression which uses only two symbols: typically "0" (zero) and "1" ( one). The base-2 numeral system is a positional notatio ...

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 operation In computer programming, a bitwise operation operates on a bit string, a bit array or a binary numeral (considered as a bit string) at the level of its individual bits. It is a fast and simple action, basic to the higher-level arithmetic operati ...

s 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. Spinrad states the total time for this algorithm as .

In infinite graphs

The

computability Computability is the ability to solve a problem in an effective manner. It is a key topic of the field of computability theory within mathematical logic and the theory of computation within computer science. The computability of a problem is close ...

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 In mathematics, a set is countable if either it is finite or it can be made in one to one correspondence with the set of natural numbers. Equivalently, a set is ''countable'' if there exists an injective function from it into the natural numbers; ...

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

Every finite

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 In geometry, a diameter of a circle is any straight line segment that passes through the center of the circle and whose endpoints lie on the circle. It can also be defined as the longest chord of the circle. Both definitions are also valid for ...

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 graph In the mathematical field of graph theory, a vertex-transitive graph is a graph in which, given any two vertices and of , there is some automorphism :f : G \to G\ such that :f(v_1) = v_2.\ In other words, a graph is vertex-transitive i ...

s that are not complete graphs. A

in a graph is a vertex that is adjacent to all other vertices. Whenever a graph has a

, 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 In mathematics, the term "almost all" means "all but a negligible amount". More precisely, if X is a set, "almost all elements of X" means "all elements of X but those in a negligible subset of X". The meaning of "negligible" depends on the math ...

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. 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. 4-cube t3 B2

The hereditarily cop-win graphs are the graphs in which every

isometric The term ''isometric'' comes from the Greek for "having equal measurement". isometric may mean: * Cubic crystal system, also called isometric crystal system * Isometre, a rhythmic technique in music. * "Isometric (Intro)", a song by Madeon from ...

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 cycle In the mathematical area of graph theory, an induced path in an undirected graph is a path that is an induced subgraph of . That is, it is a sequence of vertices in such that each two adjacent vertices in the sequence are connected by an edge ...

s. 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 originally called ''Puck Man'' in Japan, is a 1980 maze action video game developed and released by Namco for arcades. In North America, the game was released by Midway Manufacturing as part of its licensing agreement with Namco America. Th ...

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 . Another early reference is the work of , 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 .

References

{{reflist, refs= {{citation , last1 = Aigner , first1 = M. , last2 = Fromme , first2 = M. , issue = 1 , journal =

Discrete Applied Mathematics ''Discrete Applied Mathematics'' is a peer-reviewed scientific journal covering algorithmic and applied areas of discrete mathematics. It is published by Elsevier and the editor-in-chief is Endre Boros (Rutgers University). The journal was split ...

, mr = 739593 , pages = 1–11 , title = A game of cops and robbers , doi = 10.1016/0166-218X(84)90073-8 , volume = 8 , year = 1984, doi-access = free {{citation , last1 = Anstee , first1 = R. P. , last2 = Farber , first2 = M. , doi = 10.1016/0095-8956(88)90093-7 , issue = 1 , journal =

Journal of Combinatorial Theory The ''Journal of Combinatorial Theory'', Series A and Series B, are mathematical journals specializing in combinatorics and related areas. They are published by Elsevier. ''Series A'' is concerned primarily with structures, designs, and applicat ...

, mr = 923263 , pages = 22–28 , series = Series B , title = On bridged graphs and cop-win graphs , volume = 44 , year = 1988, doi-access = free {{citation , last1 = Bonato , first1 = A. , last2 = Golovach , first2 = P. , last3 = Hahn , first3 = G. , last4 = Kratochvíl , first4 = J. , author4-link = Jan Kratochvíl , doi = 10.1016/j.disc.2008.04.004 , issue = 18 , journal =

Discrete Mathematics Discrete mathematics is the study of mathematical structures that can be considered "discrete" (in a way analogous to discrete variables, having a bijection with the set of natural numbers) rather than "continuous" (analogously to continuous f ...

, mr = 2567962 , pages = 5588–5595 , title = The capture time of a graph , volume = 309 , year = 2009, doi-access = free {{citation , last1 = Bonato , first1 = Anthony , last2 = Kemkes , first2 = Graeme , last3 = Prałat , first3 = Paweł , doi = 10.1016/j.disc.2012.02.018 , doi-access = free , issue = 10 , journal =

, mr = 2901161 , pages = 1652–1657 , title = Almost all cop-win graphs contain a universal vertex , volume = 312 , year = 2012 For the fact that a strong product of paths is cop-win, see {{harvtxt, Nowakowski, Winkler, 1983. For the fact that the king's graph is a strong product of paths, see {{citation , last1 = Berend , first1 = Daniel , last2 = Korach , first2 = Ephraim , last3 = Zucker , first3 = Shira , contribution = Two-anticoloring of planar and related graphs , contribution-url = http://www.emis.de/journals/DMTCS/pdfpapers/dmAD0130.pdf , location = Nancy , mr = 2193130 , pages = 335–341 , publisher = Association for Discrete Mathematics & Theoretical Computer Science , series = Discrete Mathematics & Theoretical Computer Science Proceedings , title = 2005 International Conference on Analysis of Algorithms , year = 2005 {{citation , last1 = Bonato , first1 = Anthony , last2 = Nowakowski , first2 = Richard J. , doi = 10.1090/stml/061 , isbn = 978-0-8218-5347-4 , mr = 2830217 , publisher = American Mathematical Society , location = Providence, RI , series = Student Mathematical Library , title = The Game of Cops and Robbers on Graphs , volume = 61 , year = 2011 {{citation , last = Chepoi , first = Victor , doi = 10.1137/S0895480195291230 , issue = 3 , journal = SIAM Journal on Discrete Mathematics , mr = 1628110 , pages = 414–436 , title = On distance-preserving and domination elimination orderings , volume = 11 , year = 1998 {{citation , last = Chepoi , first = Victor , doi = 10.1006/jctb.1996.1726 , issue = 1 , journal =

, mr = 1426753 , pages = 97–100 , series = Series B , title = Bridged graphs are cop-win graphs: an algorithmic proof , volume = 69 , year = 1997, doi-access = free {{citation , last = Gavenčiak , first = Tomáš , doi = 10.1016/j.disc.2010.01.015 , issue = 10–11 , journal =

, mr = 2601265 , pages = 1557–1563 , title = Cop-win graphs with maximum capture-time , volume = 310 , year = 2010, doi-access = free {{citation , last1 = Hahn , first1 = Geňa , last2 = Laviolette , first2 = François , last3 = Sauer , first3 = Norbert , last4 = Woodrow , first4 = Robert E. , doi = 10.1016/S0012-365X(02)00260-1 , issue = 1–3 , journal =

, mr = 2002070 , pages = 27–41 , title = On cop-win graphs , volume = 258 , year = 2002, doi-access = free {{citation , last1 = Lin , first1 = Min Chih , last2 = Soulignac , first2 = Francisco J. , last3 = Szwarcfiter , first3 = Jayme L. , arxiv = 1005.2211 , doi = 10.1016/j.tcs.2011.12.006 , journal =

Theoretical Computer Science Theoretical computer science (TCS) is a subset of general computer science and mathematics that focuses on mathematical aspects of computer science such as the theory of computation, lambda calculus, and type theory. It is difficult to circumsc ...

, mr = 2891574 , pages = 75–90 , title = Arboricity, {{mvar, h-index, and dynamic algorithms , volume = 426–427 , year = 2012 , s2cid = 15827218 {{citation , last1 = Lubiw , first1 = Anna , author1-link = Anna Lubiw , last2 = Snoeyink , first2 = Jack , last3 = Vosoughpour , first3 = Hamideh , arxiv = 1601.01298 , doi = 10.1016/j.comgeo.2017.07.001 , journal =

Computational Geometry Computational geometry is a branch of computer science devoted to the study of algorithms which can be stated in terms of geometry. Some purely geometrical problems arise out of the study of computational geometric algorithms, and such problems ar ...

, mr = 3693353 , pages = 14–27 , title = Visibility graphs, dismantlability, and the cops and robbers game , volume = 66 , year = 2017 {{citation , last1 = Nowakowski , first1 = Richard , last2 = Winkler , first2 = Peter , author2-link = Peter Winkler , doi = 10.1016/0012-365X(83)90160-7 , issue = 2–3 , journal =

, mr = 685631 , pages = 235–239 , title = Vertex-to-vertex pursuit in a graph , volume = 43 , year = 1983, doi-access = free {{citation , last = Quilliot , first = Alain , language = fr , pages = 131–145 , publisher =

Pierre and Marie Curie University Pierre and Marie Curie University (french: link=no, Université Pierre-et-Marie-Curie, UPMC), also known as Paris 6, was a public university, public research university in Paris, France, from 1971 to 2017. The university was located on the Jussi ...

, series = Thèse de 3ème cycle , title = Jeux et pointes fixes sur les graphes , trans-title = Games and fixed points on graphs , year = 1978, as cited by {{harvtxt, Bonato, Nowakowski, 2011 {{citation , last = Spinrad , first = Jeremy P. , doi = 10.1016/S0166-218X(03)00295-6 , issue = 1–2 , journal =

, mr = 2057611 , pages = 203–213 , title = Recognizing quasi-triangulated graphs , volume = 138 , year = 2004, doi-access = free {{citation , last1 = Seymour , first1 = Paul D. , author1-link = Paul Seymour (mathematician) , last2 = Thomas , first2 = Robin , author2-link = Robin Thomas (mathematician) , doi = 10.1006/jctb.1993.1027 , doi-access = free , issue = 1 , journal =

Journal of Combinatorial Theory, Series B The ''Journal of Combinatorial Theory'', Series A and Series B, are mathematical journals specializing in combinatorics and related areas. They are published by Elsevier. ''Series A'' is concerned primarily with structures, designs, and applicat ...

, pages = 22–33 , title = Graph searching and a min-max theorem for tree-width , volume = 58 , year = 1993 {{citation , last = Stahl , first = Rachel D. , date = September 2021 , doi = 10.1007/s00153-021-00794-3 , journal =

Archive for Mathematical Logic '' Archive for Mathematical Logic'' is a peer review, peer-reviewed mathematics journal published by Springer Science+Business Media. It was established in 1950 and publishes articles on mathematical logic. Abstracting and indexing The journal is ...

, title = Computability and the game of cops and robbers on graphs, volume = 61 , issue = 3–4 , pages = 373–397 , s2cid = 244214571

External links

Dismantlable graphs
Information System on Graph Classes and their Inclusions Graph families Pursuit–evasion