[Back]

M. Abseher, B. Bliem, G. Charwat, F. Dusberger, S. Woltran:
"Computing secure sets in graphs using answer set programming";
Journal of Logic and Computation, 30 (2020), 4; 837 - 862.

Problems from the area of graph theory always served as
fruitful benchmarks in order to explore the performance of Answer Set
Programming (ASP) systems. A relatively new branch in graph theory is
concerned with so-called secure sets. It is known that verifying whether a set is secure in a graph is already co-NP-hard. The problem of enumerating all secure sets thus is challenging for ASP and its systems. In particular, encodings for this problem seem to require disjunction and also recursive aggregates. In this paper, we provide such encodings and analyze their performance using the Clingo system.

secure sets, security in graphs, alliances in graphs

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