Haven (graph theory)
Encyclopedia
In graph theory
, a haven is a way of describing a strategy
for an evader to win a certain type of pursuit-evasion
game on an undirected graph. Havens were first introduced by ; they may also be used to characterize the treewidth of graphs and to prove the existence of small separators
on minor-closed families of graphs
.
of the subgraph of G formed by deleting X. A haven of order k in G is a function β assigning an X-flap β(X) to every set X of fewer than k vertices. A haven is required to satisfy the following monotonicity property: if , and both X and Y have fewer than k vertices, then .
It is straightforward to verify by a case analysis
that this function β satisfies the required monotonicity property of a haven. If and X has fewer than two vertices, or X has two vertices that are not the two neighbors of a corner vertex of the grid, then there is only one X-flap and it contains every Y-flap. In the remaining case, X consists of the two neighbors of a corner vertex and has two X-flaps: one consisting of that corner vertex, and another (chosen as β(X)) consisting of the six remaining vertices. No matter which vertex is added to X to form Y, there will be a Y-flap with at least four vertices, which must be the unique largest flap since it contains more than half of the vertices not in Y. This large Y-flap will be chosen as β(Y) and will be a subset of β(X). Thus in each case monotonicity holds.
game in which fewer than k pursuers attempt to capture a single evader, the pursuers and evader are both restricted to the vertices of a given undirected graph, and the positions of the pursuers and evader are known to both players. At each move of the game, a new pursuer may be added to an arbitrary vertex of the graph (as long as fewer than k pursuers are placed on the graph at any time) or one of the already-added pursuers may be removed from the graph. However, before a new pursuer is added, the evader is first informed of its new location and may move along the edges of the graph to any unoccupied vertex. While moving, the evader may not pass through any vertex that is already occupied by any of the pursuers.
If a k-haven exists, then the evader may avoid being captured indefinitely, and win the game, by always moving to a vertex of β(X) where X is the set of vertices that will be occupied by pursuers at the end of the move. The monotonicity property of a haven guarantees that, when a new pursuer is added to a vertex of the graph, the vertices in β(X) are always reachable from the current position of the evader.
For instance, an evader can win this game against three pursuers on a grid by following this strategy with the haven of order 4 described in the example. However, on the same graph, four pursuers can always capture the evader, by first moving onto three vertices that split the grid onto two three-vertex paths, then moving into the center of the path containing the evader, forcing the evader into one of the corner vertices, and finally removing one of the pursuers that is not adjacent to this corner and placing it onto the evader. Therefore, the grid can have no haven of order 5.
Havens are also closely related to the existence of separator
s, small sets X of vertices in an n-vertex graph such that every X-flap has at most 2n/3 vertices. If a graph G does not have a k-vertex separator, then every set X of at most k vertices has a (unique) X-flap with more than 2n/3 vertices. In this case, G has a haven of order , in which β(X) is defined to be this unique large X-flap. That is, every graph has either a small separator or a haven of high order.
If a graph G has a haven of order k, with for some integer h, then G must also have a complete graph
Kh as a minor
. In other words, the Hadwiger number of an n-vertex graph with a haven of order k is at least k2/3n−1/3. As a consequence, the Kh-minor-free graphs have treewidth less than h3/2n1/2 and separators of size less than h3/2n1/2. More generally an O(√n) bound on treewidth and separator size holds for any nontrivial family of graphs that can be characterized by forbidden minors, because for any such family there is a constant h such that the family does not include Kh.
Graph theory
In mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. A "graph" in this context refers to a collection of vertices or 'nodes' and a collection of edges that connect pairs of...
, a haven is a way of describing a strategy
Strategy (game theory)
In game theory, a player's strategy in a game is a complete plan of action for whatever situation might arise; this fully determines the player's behaviour...
for an evader to win a certain type of pursuit-evasion
Pursuit-evasion
Pursuit-evasion is a family of problems in mathematics and computer science in which one group attempts to track down members of another group in an environment. Early work on problems of this type modeled the environment geometrically...
game on an undirected graph. Havens were first introduced by ; they may also be used to characterize the treewidth of graphs and to prove the existence of small separators
Planar separator theorem
In graph theory, the planar separator theorem is a form of isoperimetric inequality for planar graphs, that states that any planar graph can be split into smaller pieces by removing a small number of vertices...
on minor-closed families of graphs
Robertson–Seymour theorem
In graph theory, the Robertson–Seymour theorem states that the undirected graphs, partially ordered by the graph minor relationship, form a well-quasi-ordering...
.
Definition
Formally, if G is an undirected graph, and k ≥ 0 is an integer, and X is a set of at most k vertices, then an X-flap is a nonempty connected componentConnected component
Connected components are part of topology and graph theory, two related branches of mathematics.* For the graph-theoretic concept, see connected component .* In topology: connected component .Implementations:...
of the subgraph of G formed by deleting X. A haven of order k in G is a function β assigning an X-flap β(X) to every set X of fewer than k vertices. A haven is required to satisfy the following monotonicity property: if , and both X and Y have fewer than k vertices, then .
Example
As an example, let G be a nine-vertex grid graph. Define a haven of order 4 in G, mapping each set X of three or fewer vertices to an X-flap β(X), as follows:- If there is a unique X-flap that is larger than any of the other X-flaps, let β(X) be that unique large X-flap.
- Otherwise, choose β(X) arbitrarily to be any X-flap.
It is straightforward to verify by a case analysis
Case analysis
Case analysis is one of the most general and applicable methods of analytical thinking, depending only on the division of a problem, decision or situation into a sufficient number of separate cases. Analysing each such case individually may be enough to resolve the initial question...
that this function β satisfies the required monotonicity property of a haven. If and X has fewer than two vertices, or X has two vertices that are not the two neighbors of a corner vertex of the grid, then there is only one X-flap and it contains every Y-flap. In the remaining case, X consists of the two neighbors of a corner vertex and has two X-flaps: one consisting of that corner vertex, and another (chosen as β(X)) consisting of the six remaining vertices. No matter which vertex is added to X to form Y, there will be a Y-flap with at least four vertices, which must be the unique largest flap since it contains more than half of the vertices not in Y. This large Y-flap will be chosen as β(Y) and will be a subset of β(X). Thus in each case monotonicity holds.
Pursuit-evasion
Havens model a certain class of strategies for an evader in a pursuit-evasionPursuit-evasion
Pursuit-evasion is a family of problems in mathematics and computer science in which one group attempts to track down members of another group in an environment. Early work on problems of this type modeled the environment geometrically...
game in which fewer than k pursuers attempt to capture a single evader, the pursuers and evader are both restricted to the vertices of a given undirected graph, and the positions of the pursuers and evader are known to both players. At each move of the game, a new pursuer may be added to an arbitrary vertex of the graph (as long as fewer than k pursuers are placed on the graph at any time) or one of the already-added pursuers may be removed from the graph. However, before a new pursuer is added, the evader is first informed of its new location and may move along the edges of the graph to any unoccupied vertex. While moving, the evader may not pass through any vertex that is already occupied by any of the pursuers.
If a k-haven exists, then the evader may avoid being captured indefinitely, and win the game, by always moving to a vertex of β(X) where X is the set of vertices that will be occupied by pursuers at the end of the move. The monotonicity property of a haven guarantees that, when a new pursuer is added to a vertex of the graph, the vertices in β(X) are always reachable from the current position of the evader.
For instance, an evader can win this game against three pursuers on a grid by following this strategy with the haven of order 4 described in the example. However, on the same graph, four pursuers can always capture the evader, by first moving onto three vertices that split the grid onto two three-vertex paths, then moving into the center of the path containing the evader, forcing the evader into one of the corner vertices, and finally removing one of the pursuers that is not adjacent to this corner and placing it onto the evader. Therefore, the grid can have no haven of order 5.
Connections to treewidth, separators, and minors
Havens may be used to characterize the treewidth of graphs: a graph has a haven of order k if and only if it has treewidth at least . A tree decomposition may be used to describe a winning strategy for the pursuers in the same pursuit-evasion game, so it is also true that a graph has a haven of order k if and only if the evader wins with best play against fewer than k pursuers. In games won by the evader, there is always an optimal strategy in the form described by a haven, and in games won by the pursuer, there is always an optimal strategy in the form described by a tree decomposition. For instance, because the grid has a haven of order 4, but does not have a haven of order 5, it must have treewidth exactly 3.Havens are also closely related to the existence of separator
Planar separator theorem
In graph theory, the planar separator theorem is a form of isoperimetric inequality for planar graphs, that states that any planar graph can be split into smaller pieces by removing a small number of vertices...
s, small sets X of vertices in an n-vertex graph such that every X-flap has at most 2n/3 vertices. If a graph G does not have a k-vertex separator, then every set X of at most k vertices has a (unique) X-flap with more than 2n/3 vertices. In this case, G has a haven of order , in which β(X) is defined to be this unique large X-flap. That is, every graph has either a small separator or a haven of high order.
If a graph G has a haven of order k, with for some integer h, then G must also have a complete graph
Complete graph
In the mathematical field of graph theory, a complete graph is a simple undirected graph in which every pair of distinct vertices is connected by a unique edge.-Properties:...
Kh as a minor
Minor (graph theory)
In graph theory, an undirected graph H is called a minor of the graph G if H is isomorphic to a graph that can be obtained by zero or more edge contractions on a subgraph of G....
. In other words, the Hadwiger number of an n-vertex graph with a haven of order k is at least k2/3n−1/3. As a consequence, the Kh-minor-free graphs have treewidth less than h3/2n1/2 and separators of size less than h3/2n1/2. More generally an O(√n) bound on treewidth and separator size holds for any nontrivial family of graphs that can be characterized by forbidden minors, because for any such family there is a constant h such that the family does not include Kh.