[Back]

F. Dusberger, M. Abseher, B. Bliem, G. Charwat, S. Woltran:
"Computing Secure Sets in Graphs using Answer Set Programming";
Journal of Logic and Computation, 2015 special issue (2015), 2015 special issue; 1 - 26.

The notion of secure sets is a rather new concept in the area of graph theory. Applied to social network analysis, the goal is to identify groups of entities that can repel any attack or influence from the outside. In this article, we tackle this problem by utilizing Answer Set Programming (ASP). It is known that verifying whether a set is secure in a graph is already co-NP-hard. Therefore, the problem of enumerating all secure sets is challenging for ASP and its systems. In particular, encodings for this problem seem to require disjunction and also recursive aggregates. Here, we provide such encodings and analyse their performance using the Clingo system. Furthermore, we study several problem variants, including multiple secure or insecure sets, and weighted graphs.

secure sets, graphs, answer set, computing

http://dx.doi.org/10.1093/logcom/exv060

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

Project Head Stefan Woltran:
START