Eternal Vertex Cover
Abstract
Joint work with Saraswati Nanoti ⸱ To appear at CSR 2022 ⸱ Preprint available from ArXiV
Eternal Vertex Cover is a dynamic variant of the vertex cover problem. The complexity of the problem on bipartite graphs is open, as is the question of whether the problem admits a polynomial kernel. We settle both these questions by showing that Eternal Vertex Cover is NP-hard and does not admit a polynomial compression even on bipartite graphs of diameter six. We also show that the problem admits a polynomial time algorithm on the class of cobipartite graphs.