Computing Secure Sets in Graphs using Answer Set Programming

ABSTRACT. 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. In a nutshell, a subset S of vertices is secure if for each X ⊆ S the number of vertices from S that appear in the closed neighborhood of X is not smaller than the number of elements in the closed neighborhood of X not from S (where the closed neighborhood of a set of vertices contains the set itself plus all vertices adjacent to any vertex in that set). 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.