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

Consider the following non-deterministic algorithm for solving the complete bipartite subgraph problem:
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)
}

Problem 2

There is, of course, a dual algorithm that switches hubs with authorities and in-arcs with out-arcs.
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)
}
Answer parts A,B, and C from problem 1 for this new algorithm.

Problem 3

Or one can work both sides in tandem.
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)
}
Note: the "either/or" construction is a non-deterministic choice, analogous to "choose". Answer parts A and B from problem 1 for this third algorithm.

Problem 4: (Extra credit)

Describe or construct an example where the algorithm in problem 3 finds a solution much faster than the algorithmns in either problems 1 or 2.