The Minimum Eternal Vertex Cover Problem on a Subclass of Series-Parallel Graphs
Fuente:
arXiv
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866910905318506496 |
|---|---|
| author | Calamoneri, Tiziana Corò, Federico Paesani, Giacomo |
| author_facet | Calamoneri, Tiziana Corò, Federico Paesani, Giacomo |
| contents | Eternal vertex cover is the following two-player game between a defender and an attacker on a graph. Initially, the defender positions k guards on k vertices of the graph; the game then proceeds in turns between the defender and the attacker, with the attacker selecting an edge and the defender responding to the attack by moving some of the guards along the edges, including the attacked one. The defender wins a game on a graph G with k guards if they have a strategy such that, in every round of the game, the vertices occupied by the guards form a vertex cover of G, and the attacker wins otherwise. The eternal vertex cover number of a graph G is the smallest number k of guards allowing the defender to win and Eternal Vertex Cover is the problem of computing the eternal vertex cover number of the given graph.
We study this problem when restricted to the well-known class of series-parallel graphs. In particular, we prove that Eternal Vertex Cover can be solved in linear time when restricted to melon graphs, a proper subclass of series-parallel graphs. Moreover, we also conjecture that this problem is NP-hard on series-parallel graphs. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2504_04897 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | The Minimum Eternal Vertex Cover Problem on a Subclass of Series-Parallel Graphs Calamoneri, Tiziana Corò, Federico Paesani, Giacomo Combinatorics Computational Complexity Discrete Mathematics Data Structures and Algorithms 05C85, 68R10 G.2.2 Eternal vertex cover is the following two-player game between a defender and an attacker on a graph. Initially, the defender positions k guards on k vertices of the graph; the game then proceeds in turns between the defender and the attacker, with the attacker selecting an edge and the defender responding to the attack by moving some of the guards along the edges, including the attacked one. The defender wins a game on a graph G with k guards if they have a strategy such that, in every round of the game, the vertices occupied by the guards form a vertex cover of G, and the attacker wins otherwise. The eternal vertex cover number of a graph G is the smallest number k of guards allowing the defender to win and Eternal Vertex Cover is the problem of computing the eternal vertex cover number of the given graph. We study this problem when restricted to the well-known class of series-parallel graphs. In particular, we prove that Eternal Vertex Cover can be solved in linear time when restricted to melon graphs, a proper subclass of series-parallel graphs. Moreover, we also conjecture that this problem is NP-hard on series-parallel graphs. |
| title | The Minimum Eternal Vertex Cover Problem on a Subclass of Series-Parallel Graphs |
| topic | Combinatorics Computational Complexity Discrete Mathematics Data Structures and Algorithms 05C85, 68R10 G.2.2 |
| url | https://arxiv.org/abs/2504.04897 |