Complexity of Eternal Security

Abstract

We show that deciding if a set of vertices is an eternal $1$-secure set is complete for $\text{co-}N{P}^{\text{NP}}$, solving a problem stated by Goddard, Hedetniemi, and Hedetniemi $[JCMCC,\text{vol. 52},\text{pp. 160-180}]$.