The Rail Guardians

Introduction

The Rail Guardians is an interactive implementation of the Eternal Vertex Cover (EVC) problem from graph theory.

A vertex cover is a subset of vertices such that every edge in a graph has at least one endpoint in that subset. For a graph G(V, E), the size of the smallest such subset is the minimum vertex cover, denoted mvc(G).

In the dynamic setting, the problem becomes a defender-attacker game. The defender places guards on vertices and the attacker chooses edges to attack. An attack is defended only if a guard can move along the attacked edge. The minimum number of guards that guarantees perpetual defense is the eternal vertex cover number, denoted evc(G).

Background

Eternal Vertex Cover was introduced by Klostermeyer and Mynhardt [2], with the classical bound mvc(G) ≤ evc(G) ≤ 2mvc(G). Subsequent work explored structural graph classes, grids, complexity, and approximation behavior [3][4][5][6]. This project focuses on making that theory playable and intuitive through a clean browser-based strategy game.

The Rail Guardians

The Rail Guardians is a two-player web game where the defender protects railway tracks (edges) and the attacker attempts to break them. The game mechanics follow the formal EVC rules while keeping the interaction fast and visual.

Storyline

You lead railway operations in a high-risk setting with frequent sabotage attempts. Your objective is to deploy builders (guards) so that every track stays defendable against an attacker's move sequence.

Mode 1: Generic Eternal Vertex Cover

This baseline mode implements the standard EVC gameplay. The defender places builders first and then alternates turns with the attacker. If an unguarded edge is attacked, the attacker wins. Otherwise, the defender must respond with a valid movement and survive the configured number of rounds.

Mode 2: Partial-Visibility Memory Challenge

The same core rules apply, but the defender does not see the full graph at once. Local neighborhood information is revealed contextually, requiring memory and strategic planning under uncertainty.

Mode 3: Energy-Aware Eternal Vertex Cover

Each builder has limited energy. Moving a builder reduces its energy, and pass moves also consume energy from the strongest remaining builder. The game ends when any builder reaches zero energy or when an undefendable attack happens. The score is the number of rounds survived.

Analysis of Max Score for Energy Aware EVC

For the energy-aware variant (Mode 3), the project includes an analysis of maximum achievable defender score on linear path graphs when each builder starts with energy K (for large K). The objective is to understand how graph size and builder count affect survivability.

Table 1: Max score trends for Energy-Aware Eternal Vertex Cover on path graphs.

Key observations:

• As builder count approaches the number of stations needed for robust coverage, the score scales approximately linearly with K.
• Undersupplied configurations collapse quickly regardless of large initial energy.
• Optimal initial placement matters as much as movement policy in long-horizon play.
• The energy-aware mode creates a clear trade-off between immediate defense and long-term sustainability.

Conclusion

The Rail Guardians presents Eternal Vertex Cover as an interactive strategy experience without diluting the underlying graph-theoretic rules. It combines formal gameplay constraints with a clear UI and progressively challenging modes.

Future extensions include stronger AI agents, larger graph families, and heuristic or genetic approaches for maximizing score in the energy-aware setting.

Acknowledgements

Thanks to Prof. Neeldhara Misra, Prof. Jyothi Krishnan, and Saraswati Girish Nanoti for helpful discussions on the problem setting, and to Sakshi for contribution to the storyline.

References

1. “Vertex cover,” Wikipedia. Mar. 01, 2024. Accessed: Apr. 26, 2024. [Online]. Available: https://en.wikipedia.org/w/index.php?title=Vertex_cover&oldid=1211245782
2. W. F. Klostermeyer and C. M. Mynhardt, “Edge protection in graphs”.
3. T. Calamoneri and F. Corò, “(Eternal) Vertex Cover Number of Infinite and Finite Grid Graphs.” arXiv, Sep. 12, 2022. doi: 10.48550/arXiv.2209.05102.
4. J. Babu, L. S. Chandran, M. Francis, V. Prabhakaran, D. Rajendraprasad, and J. N. Warrier, “On Graphs with Minimal Eternal Vertex Cover Number,” in Algorithms and Discrete Applied Mathematics, S. P. Pal and A. Vijayakumar, Eds., Cham: Springer International Publishing, 2019, pp. 263–273. doi: 10.1007/978-3-030-11509-8_22.
5. F. V. Fomin, S. Gaspers, P. A. Golovach, D. Kratsch, and S. Saurabh, “Parameterized algorithm for eternal vertex cover,” Inf. Process. Lett., vol. 110, no. 16, pp. 702–706, Jul. 2010, doi: 10.1016/j.ipl.2010.05.029.
6. J. Babu, N. Misra, and S. G. Nanoti, “Eternal Vertex Cover on Bipartite Graphs,” in Computer Science – Theory and Applications, A. S. Kulikov and S. Raskhodnikova, Eds., Cham: Springer International Publishing, 2022, pp. 64–76. doi: 10.1007/978-3-031- 09574-0_5.