Encoding Class Reachability

Class Tree
Description Reachability is one of the best studied problems in computer science. Instances of the eachability problem occurr, directly or indirectly, in a lot of relevant real world applications, ranging from databases to product configurations and networks. Importantly, the minimality-based semantics of ASP, makes ASP well suited to naturally and efficiently encode Reachability, which is the problem where ASP is much better than SAT and CSP.

Given a directed graph G=(V,E) the solution to the Reachability problem reachable(a,b) determines wether a node b in V is reachable from a node a in
V through a sequence of edges in E. The input is provided by a relation edge(X,Y) where a fact edge(a,b) states that b is directly reachable by and edge from a.

In database terms, determining all pairs of reachable nodes in G amounts to computing the
transitive closure of the relation storing the edges.

In order to make Reachability a decisional problem it is necessary to fix a specific pair of nodes, a and b, and determine wether b is reachable from a. In particular, we require to check wether, on the benchmark instances of the ASP contest, reachable(10380, 10189) is true or not.

Input format:
Each input graph is represented by the set of its edges.The predicate used to define edges is a binary predicate "edge" where edge(a,b) means that there is a directed edge going from a to b:

edge(1,3).
edge(4,2).

Author: Giorgio Terracina
Encodings
1 - 4 of 4