The problem of finding a clique of specified size K in a graph can be formulated as a state space search as follows: Impose a specified ordering on the vertices in the graph (e.g. alphabetical). Then

- A state is a clique.
- A operator on clique Z is to add a vertex V that is connected to all the vertices in Z, and that is later than all of Z in the ordering of vertices. For instance, if Z is the set { A,D } then the possible operators are adding E, adding G, and adding H.
- The start state is the empty set. (The operators on the empty set allow you to add any single vertex.)
- The goal state is a clique of size K.

A. Is this state space a tree?

**Answer:** Yes it is. Because of the restriction that the vertices are
added according to a fixed order, any given state can be created from the
start state only by the operations of adding the vertices in order. For
example, the state { A,D,E } can only be created by the three operations
``Add A; add D; add E'' in that order.

B. What is the maximum branching factor?

**Answer:** The maximum branching factor is attained at the root,
and is equal to the number of vertices in the graph (8 in this example.)

C. What is the distance from the start state to the goal states,
if any exist?

**Answer:** A goal state with K vertices is the result of K operations.
Hence, the distance from the start state to the goal state is K (4 in this
instance.)

D. Give an upper bound on the number of states in the state space.

**Answer:** A crude bound: As the branching factor is bounded by V
(the number of vertices in the graph) and the depth of the tree is K,
the number of states is less than V^{K}.

A better bound: A set of size V has C(V,I) = V!/I!(V-I)! subsets of size I. Hence since every state in the state space is a subset of the graph of size at most K, the size of the state space is at most the sum over I from 0 to K of V!/I!(V-I)!.

E. Suppose that we search the space using a depth first search.
What is the first solution found to the problem ``Find a clique of size 3''
in the above graph?

** Answer:** { A,D,E }.

What is the first solution found to the problem ``Find a clique of size 4''
in the above graph? \\
**Answer:** { B,C,F,G }.

- A state is a stack of queries.
- An operator on a state S does the following: It pops the query Q off the top of S; finds a rule R whose head matches Q under variable bindings B; pushes all of queries in the tail of Q onto S from end to beginning; and applies bindings B to all the queries in S.
- The goal state is the stack containing only the top-level query (the user's query).
- The end state is the empty stack.

p(X,b) :- r(X,Y), s(Y), t(X,Y). Then one operator on the state is the following

- Pop p(a,W) off the stack
- As usual, rename the variables in the rule to be X1 and Y1.
- Match the query p(a,W) with the head of the rule p(X1,b) under the bindings W=b, X1=a.
- Push the tail of the rule onto the stack and apply the bindings.

Note: The entire procedure above is *one* operator in the search
space.

A. Suppose that there are P predicates, a maximum of R rules per predicate, and a maximum of T subqueries in the tail of a rule. What is the maximum branching factor in the search space?

**Answer:** The operators possible in any given state correspond to
the rules that match the query at the top of the stack. Hence, the
branching factor is R.

B. Suppose we have the following Prolog code:

r(X,X). r(a,b). r(b,c). s(b). s(c). t(a,a). t(X,Y) :- s(Y), r(Y,X). p(X,Y) :- s(X), r(Y,X). p(X,b) :- r(X,Y), s(Y), t(X,Y).Draw the search space corresponding to the top-level query ``?-p(a,Z).''