Complexity of Secure Sets
Bernhard Bliem, Stefan Woltran · Lecture notes in computer science · 2016
A secure set S in a graph is defined as a set of vertices such that for any $$X\subseteq S$$ the majority of vertices in the neighborhood of X belongs to S. It is known that deciding whether a set S is secure in a graph is $$\text {co-}\hbox {NP}$$ -complete. However, it is still open how this result contributes to the actual complexity of deciding whether, for a given graph G and integer k, a non-empty secure set for G of size at most k exists. While membership in the class $$\Sigma ^{\mathrm{P}}_{2}$$ is rather easy to see for this existence problem, showing $$\Sigma ^{\mathrm{P}}_{2}$$ -hardness is quite involved. In this paper, we provide such a hardness result, hence classifying the secure set existence problem as $$\Sigma ^{\mathrm{P}}_{2}$$ -complete. We do so by first showing hardness for a variantof the problem, which we then reduce step-by-step to secure set existence. In total, we obtain eight new completeness results for different variants of the secure set existence problem.