Description
Question 1 Spanning spiders
A spanning tree of a graph is a subgraph that is a tree and contains all the vertices of the original
graph. A spider is a tree with at most one vertex whose degree is 3 or more, this vertex is called
the center of the spider. If there is no vertex with degree 3 or more, then any vertex can be the
center. A leg of the spider is a path from the center to a vertex of degree 1.
In this exercise, we are interested in creating a program to find spanning spiders of input graphs:
for any graph, we want to identify a subgraph that is a spanning tree and also a spider.
This exercise is inspired from one of the questions in the 2003 Prolog Programming Contest.1
The goal is to write an Answer Set Program such that given a graph as input, every stable model
corresponds to a distinct spanning spider. Not every graph has a spanning spider, so if an input
graph does not admit any spanning spider, the corresponding program should be unsatisfiable.
a
b
c
d
e
x
y
z
Figure 1: Example graph
Input format An input file contains predicate instances of vertex/1 indicating the vertices of
the graph and predicate instances of edge/2 indicating the edges of the graph.
Output format Your program should compute a model containing a predicate leg/2 indicating
which edges are included in the spanning spider, as well as a predicate center/1 indicating which
vertex is the center of the spider.
vertex ( a ).
vertex ( b ).
vertex ( c ).
vertex ( d ).
vertex ( e ).
vertex ( x ).
vertex ( y ).
vertex ( z ).
edge (a , d ).
edge (a , x ).
edge (b , d ).
edge (b , y ).
1https://people.cs.kuleuven.be/~bart.demoen/PrologProgrammingContests/Contest2003.html
edge (c , d ).
edge (c , z ).
edge (d , e ).
edge (e , x ).
edge (x , z ).
edge (y , z ).
1.1 Does the graph in Figure 1 have any spanning spider? If yes, indicate the center vertex and
the list of edges included in the spanning spider.
1.2 Provide ASP rules that define the center/1 predicate and ensure that in any model, exactly
one vertex is selected as the center.
1.3 Provide a generator for the leg/2 predicate.
1.4 One property required of spanning spiders is that every vertex should be reachable from
the center through leg edges. Introduce a derived predicate reachable/1 that ranges over vertex
names and is true when the corresponding vertex is reachable from the center through leg edges.
Use this predicate to define a constraint that ensures every vertex of the original graph is reachable
from the center through leg edges.
1.5 The reachability of every vertex from the center is a required property of spanning spiders,
but it is not sufficient and we need to ensure other constraints are satisfied. Describe all the other
constraints that need to be satisfied and write ASP rules to enforce these constraints.
1.6 Based on your answers to the above questions, write an ASP program spiders.lp that
takes an input graph and outputs all the distinct spanning spiders of the graph. How many
distinct spanning spiders does the graph in Figure 1 have?
1.7 Spanning spiders with short legs. Write an ASP program spidershortlegs.lp that outputs
a spanning spider with the shortest longest leg.
2
