B. Bliem, S. Woltran:

"Complexity of Secure Sets";

Talk: International Workshop on Graph-Theoretic Concepts in Computer Science (WG), Garching, Germany; 2015-06-17 - 2015-06-19; in: "Proceedings of the 41st International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2015)", E. Mayr (ed.); LNCS/Springer, 9224 (2016), ISBN: 978-3-662-53173-0; 64 - 77.

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 co-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^{P}_{2} is rather easy to see for this existence problem, showing \Sigma^{P}_{2}-hardness is quite involved. In this paper, we provide such a hardness result, hence classifying the secure set existence problem as \Sigma^{P}_{2}-complete. We do so by first showing hardness for a variant of 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.

http://dx.doi.org/10.1007/978-3-662-53174-7_5

Project Head Stefan Woltran:

Answer-Set Programming Erweiterungen für Problemlösungen auf Zerlegungen

Project Head Stefan Woltran:

START

Created from the Publication Database of the Vienna University of Technology.