Eternal vertex cover proves fixed parameter tractable for key graph measures
Structural Parameterizations for Eternal Vertex Cover
Discrete MathematicsComputational ComplexityData Structures and Algorithms
Summary
Eternal Vertex Cover is a game where guards protect connections in a network by moving around to stop attacks on edges. Figuring out the smallest number of guards to protect the network forever is very hard. The authors studied how the structure of a network helps solve this problem more easily. They found new conditions, related to breaking the network into clusters or small parts, under which they can solve or approximate the problem more efficiently.
What this means in practice
- •For network security teams: Optimize placement and movement of monitoring agents in network topologies modeled by cluster deletions to improve defense strategies.
- •For infrastructure protection planners: Develop approximate strategies for continuous defense in physical or communication network systems with decomposable structures based on vertex integrity.
A theory result. No direct application yet.
Authors
Neeldhara Misra, Sebastian Ordyniak, Giacomo Paesani, Mateusz Rychlicki
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.