Thursday 5 April 2007

Is there a bipartite analog of graph theory?

Some classical theorems involving complete graphs have analogues involving complete bipartite graphs. For example, the complete graph $K_n$ has $n^{n-2}$ spanning trees, while the complete bipartite graph $K_{m,n}$ has $n^{m-1} m^{n-1}$ spanning trees. Finding the largest complete subgraph of a graph is a standard NP-hard problem, and finding the largest (in terms of number of edges) complete bipartite subgraph of a bipartite graph is also an NP-hard problem.



But possibly the area of graph theory that has most benefited from the analogy between general graphs and bipartite graphs is matching theory. Matching theory tends to be easier in the bipartite case, but the bipartite case often gives us clues for the non-bipartite case. For example, finding a maximum matching in a bipartite graph is solvable in polynomial time, but nontrivially so, and this leads us to look for a polytime algorithm for maximum matching in a non-bipartite graph (which does exist, but is more complicated than in the bipartite case). Lovász and Plummer's Matching Theory, now back in print thanks to the American Mathematical Society, gives an excellent account of the interplay between bipartite and non-bipartite matching.

No comments:

Post a Comment