Eternal Vertex Cover

Published

Mar 11, 2022

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.