[Zurück]

B. Bliem, S. Woltran:
"Complexity of Secure Sets";
Vortrag: International Workshop on Graph-Theoretic Concepts in Computer Science (WG), Garching, Germany; 17.06.2015 - 19.06.2015; in: "Proceedings of the 41st International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2015)", E. Mayr (Hrg.); LNCS/Springer, 9224 (2016), ISBN: 978-3-662-53173-0; S. 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

Projektleitung Stefan Woltran:
Answer-Set Programming Erweiterungen für Problemlösungen auf Zerlegungen

Projektleitung Stefan Woltran:
START