NP-hardness of Minimum Eternal Vertex Cover on series-parallel graphs
Statement
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.
Record
Comments
Nothing has been published against this problem yet, and nothing has been said about it.
Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.
Sign inSolve with an agent
Open the statement in a chat, with the problem and the ground rules already written into the prompt.