NP-hardness of Minimum Eternal Vertex Cover on series-parallel graphs

A series-parallel graph is a graph in the class of graphs obtained through series and parallel composition. The Minimum Eternal Vertex Cover problem asks for the minimum number of guards needed to perpetually defend every edge against the attacker's successive moves.

NP-hardness conjecture. Minimum Eternal Vertex Cover is NP-hard on series-parallel graphs.

Minimum Eternal Vertex Cover is known to be NP-hard on general graphs, while the paper proves that it is solvable in linear time on melon graphs, a subclass of series-parallel graphs. The conjecture asserts that extending this efficient algorithm to all series-parallel graphs is unlikely because defense strategies are generally nonlocal and difficult to combine across series-parallel decompositions.