[Back]


Talks and Poster Presentations (with Proceedings-Entry):

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.



English abstract:
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.


"Official" electronic version of the publication (accessed through its Digital Object Identifier - DOI)
http://dx.doi.org/10.1007/978-3-662-53174-7_5



Related Projects:
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.