# Reachability

## Problem Description

Reachability is one of the best studied problems in computer science. Instances of the reachability problem occur{, directly or indirectly, in a lot of relevant real world applications, ranging from databases to product configurations and networks. In database terms, determining all pairs of reachable nodes in a graph G amounts to computing the transitive closure of the relation storing the edges. The version of the problem for this competition comes in terms of queries to the transitive closure of G.

Given a directed graph `G=(V,E)` and a couple `<a,b>` of nodes of `G`, the truth of the atom `reaches(a,b)` determines whether node `b` is reachable from node `a` through a sequence of edges in `E`. The input is provided by a relation `edge(X,Y)` where a fact `edge(i,j)` states that node j is directly reachable by an edge in `E` from node `i`, and by one query of the form `reaches(a,b)?`.

## Predicates

**Input**:`edge/2, reaches/2`**Output**:`yes`or`no`(intended as the propositional assertions`yes.`or`no.`)

## Input format

The 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(3,4). edge(4,2). edge(3,5). edge(2,5). reaches(1,2)?

The query is expressed as a ground atom of the binary predicate `reaches`: e.g. `reaches(a,b)?` asks whether node 'b' is reachable from node 'a'. Only ground queries are provided.

## Output format

If the answer to the input query, say, `reaches(a,b)`, is positive (i.e., b is reachable from a), then the output should be `yes.`, and `no.` otherwise.

## Example(s)

Input:

edge(1,3). edge(3,4). edge(3,5). edge(4,2). edge(2,5). reaches(1,2)?

Possible Output:

yes.

## Problem Peculiarities

**Type**: Polynomial/Query **Competition Tracks**: Both

Reachability can be considered a classic polynomial problem, not to be considered too trivial. The instance graphs will be indeed quite large: rather than modelling abilities (we expect all competitors will adopt a pretty standard encoding in the M&S track also), this problem will stress memory usage and the ability of tailoring the search space at hand to what is needed for answering the goal query only.

## Notes and updates

With respect to the Second ASP Competition, the goal query is herein made explicit by means of the `reaches(a,b)?` statement which shall be found in input instances.

## Author(s)

- Author: Carmine Dodaro
- Affiliation: University of Calabria, Italy

- Original Author: Giorgio Terracina
- Affiliation: University of Calabria, Italy