In the eternal vertex cover problem, mobile guards on the vertices of a graph are used to defend it against an infinite sequence of attacks on its edges by moving to neighbor vertices. The eternal vertex cover problem consists in determining the minimum number of necessary guards. Motivated by previous literature, in this paper, we study the vertex cover and eternal vertex cover problems on regular grids when passing from the infinite to the finite version of the same graphs, and we provide either coinciding or very tight lower and upper bounds on the number of necessary guards. To this aim, we generalize the notions of minimum vertex and minimum eternal vertex covers in order to be well-defined for infinite grids.
The eternal vertex cover problem can be described in terms of a two-player game and models a problem associated with defending the vertices of a given graph against a sequence of attacks: at the beginning of the game, the defender (which controls some guards lying on the vertices of ) chooses a placement of guards on a subset of vertices of , defining an initial configuration. Subsequently, in each round of the game, the attacker attacks an edge of their choice. To repel an attack, a guard from an incident vertex moves across the attacked edge to defend it; at the same time, other guards may either remain where they are or move to neighbor vertices. If the defender is able to do this, then the attack has been successfully defended, and the game proceeds to another round, with the attacker choosing the next edge to attack. Otherwise, the attacker wins.
Graph protection has its historical roots in the time of the ancient Roman Empire [
If the defender is able to continue defending against any infinite sequence of attacks on with guards, then we say that there is a defense strategy on with guards. This strategy requires that the set of vertices containing guards is a vertex cover before and after each round. In this case, the set of positions of all the guards in any round of the game defines a configuration, referred to as an eternal vertex cover of of size .
The eternal vertex cover problem on a graph requires finding the minimum value of for which a defense strategy on with guards exists. Such minimum is denoted by ∞().
Literature. The problem was first formulated in 2009 by Klostermeyer and Mynhardt [ 3] and, in the same article, it was shown that, for any graph , () ≤ ∞() ≤ 2 (), where () is the cardinality of a minimum vertex cover for .
The problem has been deeply studied from a computational complexity point of view: deciding whether guards can protect all the edges of a graph is NP-hard [4] and remains NP-hard even for internally triangulated planar graphs [5]; moreover, it is APX-hard and there is a 2-approximation algorithm; finally, exact (exponential) algorithms are given. Recently, it was shown that the problem remains NP-hard even for bipartite graphs [6].
Nevertheless, there are a number of special graphs for which the problem can be exactly solved in polynomial time: trees [3] ( ∞( ) = − | ( )| + 1, where ( ) is the number of leaves of ), cacti [7, 8], simple generalizations of trees [9] (graphs constructed by replacing each edge of a tree with an arbitrary elementary bipartite graph or by an arbitrary clique), perfect matching cycles on vertices [3] ( ∞() = () = ⌈ 2 ⌉), chordal graphs [5, 8], chain graphs, cographs, split graphs [10], and × grids [3] (whose ∞ is 2 = if is even and is ⌈ 2 ⌉ = + 1 if , > 1 are odd with ≥ ).
More in general, in [
Finally, there are a number of papers (e.g. [12, 13, 5, 14]) connecting and ∞ of special graphs with other parameters such that the (eternal) domination number, the vertex connectivity number, and the minimum cardinality of a vertex cover that contains all cut vertices.
In this extended abstract we consider first infinite regular grids , i.e. infinite plane graphs in which all faces are identical regular polygons: hexagonal, squared, and triangular grids, here denoted by Δ, where Δ represents the degree that is equal to 3,4,6, respectively. For completeness, we also study the regular grid of degree 8, called octagonal grid (also known as “king’s graph”), and denoted by 8.
Then we study also finite portions of infinite grid graphs, that are induced by the vertices of a set of regular faces contained into a ℎ × rectangle with sides parallel to the axes and vertices at (a) hexagonal grid (b) squared grid (c) triangular grid (d) octagonal grid integer coordinates, ℎ, ∈ N; we will call these subgraphs as finite rectangular grids and denote them with Δ(ℎ, ). Clearly, this concept is not well defined for octagonal grids since they are not planar graphs, but it is not dificult to extend it (for example by momentarily removing bottom-right to up-left edges, determining the subgraph according to the definition, and then adding again the removed edges). Moreover, we assume the finite grids do not degenerate in simpler structures (and hence, e.g. the cases ℎ = 1 and = 1 are not allowed in any grid, while the case ℎ < 4 is not allowed in the hexagonal grid).
We now give a formal definition of the problems we want to study on infinite and finite grids. It is worth noting that, while the following definitions are very well known in the case of finite graphs, we need to extend them in order to make them work on infinite grids. Definition 1. Given a (either finite or infinite) graph = (, ), a vertex cover for is a set of vertices ⊆ that includes at least one endpoint of every edge. If is a finite graph, the vertex cover problem consists in finding a vertex cover of minimum cardinality, and this number is denoted with (). If is an infinite grid, the vertex cover problem consists in finding a vertex cover such that there exists 0 > 0 and, for every ≥ 0 there is a finite rectangular grid of , (, ) with a vertex set (), such that ∩ () is a minimum vertex cover for (, ).
In both cases, we will say that a solution to the vertex cover problem is a minimum vertex cover.
Given a vertex cover for , an attack may occur on a single edge = {, }, where ∈ ; a defense by to the attack on the edge is a one-to-one function : → such that: (1) () = , and (2) for each ∈ ∖ {}, () ∈ [] where [] is the close neighborhood of .
Given any vertex ∈ , we say that the guard on shifts to () and, by extension, shifts to ′ where ′ = { () s.t. ∈ }.
Since an attack of an edge whose both its extremes contain a guard can always be repelled without changing the configuration of guards (simply swapping the position of the guards on that edge), we only consider attacks on edges with one unguarded vertex.
Definition 2. Given a (either finite or infinite) graph = (, ), a vertex cover for is an eternal vertex cover if every (possibly infinite) sequence of attacks can be defended, that is if a defense shifts in ′ and ′ is an eternal vertex cover. If is a finite graph, the eternal vertex cover problem consists in finding an eternal vertex cover of minimum cardinality, and this number is denoted by ∞(). If is an infinite grid, the eternal vertex cover problem consists in finding an eternal vertex cover such that there exists 0 > 0 and, for every ≥ 0 there are (possibly coinciding) finite rectangular grids of , (, ) and ′(, ) with vertex set () and ′(), such that ∩ () and ′ ∩ ′() are minimum vertex covers for (, ) and ′(, ), respectively.
In both cases, we will say that a solution to the eternal vertex cover problem is a minimum eternal vertex cover.
In order to compare the results we obtain for finite and infinite graphs, we introduce the definitions of and ∞.
Definition 3. Let be a finite graph. We call the ratio between the number of vertices in a minimum vertex cover and the number of all the vertices of , and ∞ the ratio between the number of vertices in an eternal minimum vertex cover and the number of all the vertices of .
Let be an infinite grid, and be a minimum vertex cover and an eternal minimum vertex cover, respectively, for . For each > 0 consider every possible finite rectangular grid (, ) and let () be its vertex set; compute the minimum over all finite grids of the ratio between | () ∩ | (respectively | () ∩ |) and | ()| = 2. We call (respectively ∞) the limit as goes to ∞ of this ratio.
Intuitively, and ∞ represent the fraction of vertices that belong to a minimum cardinality cover.
This study arises from observing that, while the density of an eternal vertex cover of an infinite path is roughly 1/2, we have that in the finite path almost all vertices are needed ( ∞() = − 1 [3]).
On the other hand, it is immediate to see that any eternal vertex cover of the infinite squared grid puts guards alternately on its vertices; this is true also in the finite case, indeed, as we have already stated, from the literature, we know that a squared grid (i.e. the Cartesian product of two paths) has ∞ roughly equal to half of its number of vertices.
So, not all the graphs behave in the same way when passing from the infinite to the finite version. We wonder which is the behavior of some naturally innfiite graphs, that is whether we get an increase of their eternal vertex cover number when we reduce to a finite portion.
To this aim, we first consider infinite regular grid graphs. For each of them, we evaluate on which portion of the vertices it is necessary to put a guard; moreover, we consider a finite (rectangular) portion of such graphs and study the value of their ∞. Finally, we compare our results in infinite and finite cases. The results of this study are summarized in Tables 1 and 2.
It is worth noting that, to the best of our knowledge, in the literature, no generalizations are known for the notions of minimum vertex cover and eternal vertex cover of infinite graphs.
This study concludes that having a not null second dimension helps an efective defense strategy; indeed, the path remains the only graph for which ∞ is completely diferent when passing from the infinite to the finite case. Summary of the results for finite grid graphs; the lower part of the table contains results provided in this paper. The results of the last two rows related to ∞ hold for ℎ ≥ .
For the full version of the current paper, please refer to [15]. (2009) 235–250. [4] F. V. Fomin, S. Gaspers, P. A. Golovach, D. Kratsch, S. Saurabh, Parameterized algorithm for eternal vertex cover, Information Processing Letters 110 (2010) 702–706. [5] J. Babu, V. Prabhakaran, A new lower bound for the eternal vertex cover number of graphs,
J. Comb. Optim. 44 (2022) 2482–2498. [6] N. Misra, S. Nanoti, Eternal vertex cover on bipartite and co-bipartite graphs, CoRR abs/2201.03820 (2022). URL: https://arxiv.org/abs/2201.03820. arXiv:2201.03820. [7] J. Babu, V. Prabhakaran, A. Sharma, A linear time algorithm for computing the eternal vertex cover number of cactus graphs, arXiv preprint arXiv:2005.08058 (2020). [8] J. Babu, V. Prabhakaran, A. Sharma, A substructure based lower bound for eternal vertex cover number, Theor. Comput. Sci. 890 (2021) 87–104. [9] H. Araki, T. Fujito, S. Inoue, On the eternal vertex cover numbers of generalized trees, IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences 98 [10] K. Paul, A. Pandey, Some algorithmic results for eternal vertex cover problem in graphs, in: C. Lin, B. M. T. Lin, G. Liotta (Eds.), WALCOM: Algorithms and Computation - 17th International Conference and Workshops, WALCOM 2023, Hsinchu, Taiwan, March 22-24, 2023, Proceedings, volume 13973 of Lecture Notes in Computer Science, Springer, 2023, pp. 242–253. [11] J. Babu, L. S. Chandran, M. C. Francis, V. Prabhakaran, D. Rajendraprasad, J. N. Warrier, On graphs whose eternal vertex cover number and vertex cover number coincide, Discret.
Appl. Math. 319 (2022) 171–182. [12] M. Anderson, R. Brigham, J. Carrington, R. Dutton, R. Vitray, J. Yellen, Mortal and eternal vertex covers, Preprint (2012). [13] M. Anderson, R. Brigham, J. Carrington, R. Dutton, R. Vitray, J. Yellen, Graphs simultaneously achieving three vertex cover numbers, J. Combin. Math. Combin. Comput 91 (2014) 275–290. [14] W. F. Klostermeyer, C. M. Mynhardt, Graphs with equal eternal vertex cover and eternal domination numbers, Discrete Mathematics 311 (2011) 1371–1379. [15] T. Calamoneri, F. Corò, (Eternal) Vertex Cover number of infinite and finite grid graphs, arXiv preprint arXiv:2209.05102 (2022).