1.A. A state is a complete A,B bipartite graph where A =< J and B > = K. An operator on state S is to add a vertex V to the hubs the graph, and to restrict the authorities to those vertices in S that have inarcs from V. The start state is the "graph" with no hubs and where every vertex is an authority. The goal state is a complete bipartite J,M graph where M > = K.

1.B. The branching factor is W. The depth of search is J. The size
of the state space is certainly less than W^{J}

1.C. { C,F,G ; D,E}

1.D No, since the depth of the goal state is known.

2.A. A state is a complete A,B bipartite graph where A > = J and B =< K. An operator on state S is to add a vertex V to the authorities the graph, and to restrict the hubs to those vertices in S that have outarcs to V. The start state is the "graph" with no hubs and where every vertex is an authority. The goal state is a complete bipartite M,K graph where M > = J.

2.B. The branching factor is Z. The depth of search is K. The size
of the state space is certainly less than Z^{K}

2.C. The algorithm actually returns a 4,2 bipartite graph: { D,E,F,H; C,G}.

3.A. A state is a complete A,B bipartite graph where A =< J and B =< K. An operator is either to add a hub or add an authorities, so that the graph remains complete. The start state is the empty graph. The goal state is a complete J,K bipartite graph.

3.B. The branching factor is V. The depth is J+K. The size of the state space
is therefore at most V^{J+K}

Step 1: Construct a K,K complete bipartite graph. Let G be the set of hubs and H the set of authorities. Pick one hub and call it vertex A; pick one authority and call that vertex B.

Step 2: We now construct a second graph. For any N > 2K,
let c_{1} ... c_{N} be a set of hubs and x_{1} ...
x_{N} be a set of authorities connected according to the following
rule: there is an arc from c_{P} to x_{Q} just if
0 =< (P-Q) mod N < 2K-1. It is not hard to show (a) that this
has no K,K complete bipartite subgraph; (b) that algorithms 1 and 2 will
run a very long time before finding that out.

Step 3: Make a copy of the graph in step 2. Label the hubs
y_{1} ... y_{N} and label the authorities d_{1}
... d_{N}

Step 4: Join the three graphs together by identifying c_{1} with
A and d_{1} with B.

Step 5: Order the vertices alphabetically, with A and B first.

Now, if you run algorithm 1, it will begin by trying to find a good
set of hubs among the c_{i}, spend a very long time at that,
and only then move on to G;H. Similarly if you run algorithm 2, it will begin
by trying to find a good set of authorities among the d_{i}.

However, if you run algorithm 3, it will

- First choose A as a hub.
- Then choose B as an authority (it can't be an authority, because it has no outarcs.)
- Since A has been chosen a hub, we can ignore all the
d
_{i}'s since there's no arc from A to them. Similarly, since B is an authority, we can ignore all the c_{i}'s since there no arc from them to B. So we can proceed next, alphabetically, to G and H, and find the solution immediately.