Problem Set 1

Assigned: January 22:
Due: Feb. 5

For any two integers J,K, a (J,K) bipartite graph is a directed graph constructed by taking two disjoint sets of vertices, U of size J and V of size K, and constructing an arc from every vertex in U to every vertex in V. Figure 1 shows the (3,4) complete bipartite graph.

Figure 1

The COMPLETE BIPARTITE SUBGRAPH problem is the following: Given a graph G and two integers J,K, find a (J,K) complete bipartite graph which is a subgraph of G. For example in figure 2, the graph {F,C ; B,D,E} is a (2,3) complete bipartite subgraph.

Figure 2

This problem has recently become important in the context of evaluating Web pages. A popular theory is that important pages on the Web on any given subject tend to fall into two categories: authorities which have good content, and many inlinks, and hubs which have many links to good authorities. So one way to look for a rich cyber-community is to look for large bipartite graphs, which you have a large set of hubs and a large set of authorities, and all the hubs point to all the authorities. (This is not the only way, or necessarily the best way, to identify hubs and authorities.)

Problem 1

CBPS(in G: graph; J,K: integer;  out B : graph)
/* Note: this actually returns a (J,M) complete bipartite graph where
   M is at least K */

{  HH, AA : set of vertices; /* Set of hubs, authorities under consideration */

   HH := empty;
   AA := set of all vertices in G with at least J in-arcs;
   for I = 1 to J do {
     choose vertex H such that 
         H is later alphabetically than any letter in HH and
         H has at least K out-arcs to vertices in AA; 
     AA := (AA intersect the set of heads of out-arcs from H) - H;
     add H to HH; }
   return (the graph composed of HH union AA with all arcs from HH to AA)
}

• A. Characterize the above algorithm in terms of a state space search; what are the states, what are the operators, what is the start state, what are the goal states?
• B. Let W be the number of vertices in G with at least K out-arcs and let Z be the number of vertices in G with at least J in-arcs. Let V be the number of vertices in G. Give upper bounds on the branching factor, the depth of search, and the size of the state space. Your answer should be expressed in terms of the quantities J, K, V, W, and Z NOT given for the specific graph in figure 2.
• C. Suppose that the search is implemented as a depth-first search, and that the different possibilities for the "choose" are considered in alphabetical order. What is the first solution found for a (3,2) bipartite subgraph of the graph in figure 2?
• D. Is there any advantage to doing an iterative deepening search over a depth-first search? Explain your answer.

Problem 2

CBPS(in G: graph; J,K: integer;  out B : graph)
/* Note: this actually returns a (M,K) complete bipartite graph where
   M is at least J */

{  HH, AA : set of vertices; /* Set of hubs, authorities under consideration */

   AA := empty;
   HH := set of all vertices in G with at least K out-arcs;
   for I = 1 to K do {
     choose vertex A such that 
         A is later alphabetically than any letter in AA and
         A has at least J in-arcs from vertices in HH;
     HH := (HH intersect the set of tails of in-arcs into A) - A;
     add A to AA; }
   return (the graph composed of HH union AA with all arcs from HH to AA)
}

Problem 3

CBPS(in G: graph; J,K: integer;  out B : graph)

{  HH, AA : set of vertices; /* Set of hubs, authorities under consideration */
   HH := empty;
   AA := empty;
   VV := set of vertices in G;
   repeat { 
      choose vertex V in VV;
      either { 
        if (V has at least K out-arcs and |HH| < J and 
            V has an out-arc to every vertex in AA)
         then add V to HH;
         else fail; }
      or 
        if (V has at least J in-arcs and |AA| < K and 
            V has an in-arc from every vertex in HH)
         then add V to AA;
         else fail; }
       }
   return (the graph composed of HH union AA with all arcs from HH to AA)
}

Problem 4: (Extra credit)