dlee@NOTE.NSF.GOV (Der-Tsai Lee) (01/18/90)
Dear Colleagues: I have the following problem and I don't know of any solution. I thought you may be able to help. Consider a bipartite graph G=(V,E), where V is partitioned into two subsets Y and Z and E is a subset of Y x Z. I would like to find out if there exists any "efficient" algorithm that solves the following problem: Given the bipartite graph G as defined above, determine if there exists a subgraph G' of G such that G'=(V',E') where V' is partitioned into Y' and Z', Y' is a subset of Y, Z' a subset of Z, E' contains all the edges in E of the form (y,z), y in Y', z in Z', and the cardinality of Y' is NO LESS THAN that of Z'. If so, find it; otherwise, report none. In other words, one may look at a bipartite graph as a binary relation, represented as an adjacency matrix Y by Z. Entry (y,z) is 1 if (y,z) is in E; otherwise it is 0. The problem is to see if the rows and columns of the matrix can be permuted so that we have a "rectangular block" of dimension |Y'| by |Z'| such that |Y'| >= |Z'|, and the entries in these |Y'| rows that are outside the |Z'| columns are all zero's. I suppose there must be results known about the problem. If any of you can provide pointers to the solution, I'd appreciate very much. My mailing address: D.T.Lee Division of Computer & Computation Research National Science Foundation 1800 G. Street, N.W. Washington, D.C. 20550 Tel:(202)-357-7375 Fax:(202)-357-0320 e-mail:dlee@note.nsf.gov