1. Enumerate the answer sets of the following programs:

1.1:

a.

c :- not b, not d.

d :- a, not c.

1.2:

p :- not q.

q :- not r.

r :- not p.

1.3:

p :- q.

q :- not r.

{s ; t} :- p.

:- s, not t.

1.4:

x :- not y.

y :- not x.

a :- b.

b :- a.

2. Propose an ASP encoding for finding a clique of size 5 in a graph.

Assume the graph is represented with vertex/1 and edge/2 as follows:

vertex(1..99).   % 1,...99 are vertexes

edge(3,7).       % edge between 3 and 7

....

edge(X,Y) :- edge(Y,X).

3. Propose a generalization of the previous encoding to find the

largest clique in a graph.

4. Propose an ASP encoding for finding a graph coloring for the

following undirected graph:

vertex(1..6).

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

edge(2, (4;5;6)).

edge(3, (4;5)).

edge(5, 6).

5. Propose a generalization of the previous encoding to find the

smallest number of colors necessary to color the graph.

6. Propose an ASP encoding for finding a vertex cover for the

graph in 4.

7. Propose a generalization that minimizes the size of the

vertex cover for the graph.