Abseher, M., Bliem, B., Charwat, G., Dusberger, F., & Woltran, S. (2020). Computing Secure Sets in Graphs using Answer Set Programming. Journal of Logic and Computation, 30(4), 837–862. https://doi.org/10.1093/logcom/exv060
E192-02 - Forschungsbereich Databases and Artificial Intelligence E192 - Institut für Logic and Computation
-
Journal:
Journal of Logic and Computation
-
ISSN:
0955-792X
-
Date (published):
Jun-2020
-
Number of Pages:
26
-
Publisher:
OXFORD UNIV PRESS
-
Peer reviewed:
Yes
-
Keywords:
Software; Theoretical Computer Science; Hardware and Architecture; Logic; secure sets; graphs; Arts and Humanities (miscellaneous); answer set; computing
-
Abstract:
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.
en
Project title:
Extending the Answer-Set Programming Paradigm to Decomposed Problem Solving: P25607-N23 (Fonds zur Förderung der wissenschaftlichen Forschung (FWF)) START: Y 698-N23 (Fonds zur Förderung der wissenschaftlichen Forschung (FWF))
