Structural Parameterizations for Eternal Vertex Cover

Abstract

Eternal Vertex Cover (EVC) is a turn-based attacker-defender game on an undirected graph G. To begin with, the defender places k guards on vertices of G. The attacker, on their turn, can choose an edge e not already occupied at both endpoints to "attack". The edge e is defended if a guard moves along the edge e. The defender, on their turn, can move any subset of guards. A guard can only move to a neighboring vertex. The minimum number of guards needed to indefinitely defend against any sequence of attacks is called the eternal vertex cover number, generalizing the classic vertex cover number. Determining this number is NP-hard in general, motivating the study of parameterized and approximation algorithms. The problem is known to be FPT when parameterized by the cover number, but structural parameters remain relatively unexplored in the literature. In this work, we explore structural parameterizations for EVC. We show that EVC is FPT parameterized by the cluster vertex deletion number, which generalizes the previously studied parameterization by vertex cover number. We next study the problem parameterized by vertex integrity, which is the smallest number of vertices we need to delete from G so that the resulting graph is a disjoint union of constant-sized components. We first show that Eternal Vertex Cover is XP parameterized by vertex integrity. Then, we develop a polynomial-time approximation algorithm, which computes an additive 6k+1 (g(k)) approximation, where k is equal to the cluster vertex deletion number (vertex integrity). Finally, we show a FPT algorithm for when the deletion set produces "nice" connected components, which are components that are bounded in size and satisfy a technical condition.

On Eternal Connected Vertex Cover
Rajat Adak, Saraswati Girish Nanoti
arXiv30 Sep 2026PreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv
Weak and strong Lefschetz properties for vertex cover Artinian algebras associated to graphs
Trung Chau, Tran Quang Hoa, Dang Thi Kieu Uyen
arXiv29 Sep 2026PreprintarXiv licenceFull textAlgebra & number theory Combinatorics & discrete mathematicsarXiv
Energy of signed graphs and the vertex cover number
Aniruddha Samanta, Deepshikha, Kinkar Chandra Das
arXiv16 Oct 2026PreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv
Structural properties of admissible subgraphs and the depth of symbolic powers of cover ideals
Nguyen Thu Hang, Nguyen Thi Thanh Tam, Thanh Vu
arXiv7 Oct 2026PreprintCC BY-NC-SA 4.0Full textAlgebra & number theoryarXiv
A Counterexample to an Eternal Domination Conjecture
Tom Adamczewski, William F. Klostermeyer
arXiv10 Sep 2026PreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv

Cite

BibTeX RIS

BibTeX

@misc{misra2026structural,
  title = {{Structural Parameterizations for Eternal Vertex Cover}},
  author = {Neeldhara Misra and Sebastian Ordyniak and Giacomo Paesani and Mateusz Rychlicki},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2609.17891},
  eprint = {2609.17891},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.17891},
  note = {CC BY 4.0},
}

RIS

TY  - UNPB
TI  - Structural Parameterizations for Eternal Vertex Cover
AU  - Neeldhara Misra
AU  - Sebastian Ordyniak
AU  - Giacomo Paesani
AU  - Mateusz Rychlicki
PY  - 2026
DA  - 2026/09/15
PB  - arXiv
DO  - 10.48550/arxiv.2609.17891
UR  - https://arxiv.org/abs/2609.17891
AB  - Eternal Vertex Cover (EVC) is a turn-based attacker-defender game on an undirected graph G. To begin with, the defender places k guards on vertices of G. The attacker, on their turn, can choose an edge e not already occupied at both endpoints to "attack". The edge e is defended if a guard moves along the edge e. The defender, on their turn, can move any subset of guards. A guard can only move to a neighboring vertex. The minimum number of guards needed to indefinitely defend against any sequence of attacks is called the eternal vertex cover number, generalizing the classic vertex cover number. Determining this number is NP-hard in general, motivating the study of parameterized and approximation algorithms. The problem is known to be FPT when parameterized by the cover number, but structural parameters remain relatively unexplored in the literature. In this work, we explore structural parameterizations for EVC. We show that EVC is FPT parameterized by the cluster vertex deletion number, which generalizes the previously studied parameterization by vertex cover number. We next study the problem parameterized by vertex integrity, which is the smallest number of vertices we need to delete from G so that the resulting graph is a disjoint union of constant-sized components. We first show that Eternal Vertex Cover is XP parameterized by vertex integrity. Then, we develop a polynomial-time approximation algorithm, which computes an additive 6k+1 (g(k)) approximation, where k is equal to the cluster vertex deletion number (vertex integrity). Finally, we show a FPT algorithm for when the deletion set produces "nice" connected components, which are components that are bounded in size and satisfy a technical condition.
ER  -

Abstract

Related

Cite