Path: utzoo!utgpu!news-server.csri.toronto.edu!mailrus!tut.cis.ohio-state.edu!ucbvax!parc.xerox.COM!gilbert
From: gilbert@parc.xerox.COM
Newsgroups: comp.theory
Subject: Re: Finding subsets of equations
Message-ID: <9006051457.AA12147@irt.watson.ibm.com>
Date: 5 Jun 90 14:57:13 GMT
Sender: daemon@ucbvax.BERKELEY.EDU
Reply-To: gilbert%parc.xerox.com@VM1.NoDak.EDU
Lines: 55

Russell J. Abbott asked the following:

>   Does anyone have or know of a solution to the following problem?
>   Suppose you have n equations in m unknowns, m > n and want to find a
>   subset of those equations in which the number of unknowns is no greater
>   than the number of equations.  Is there a way to do that without a brute
>   force search through all possible combinations of equations with common
>   unknowns?

Martin Tompa gave a solution that calls maximum matching m times and asked:

>   This still seems like brute force to me: it would be interesting to know
>   whether the problem stated can be reduced to only one call on perfect
>   matching.


It is indeed possible to solve the problem with one call on maximum
matching.  This was essentially done by Dulmage, Mendelsohn, and
Johnson in the 1950's.  It is now used in sparse matrix computation;
see e.g. Coleman, Gilbert, and Edenbrandt, "Predicting fill for sparse
orthogonal factorization", JACM 33 (1986) pp. 517-532.

Briefly, a matrix (or bipartite graph) with more rows than columns has the
"strong Hall property" (SHP) if every nonempty subset of columns is incident
on a strictly larger set of rows.  Abbott's problem is to decide SHP for
the transpose of the matrix, and to find a certificate of non-SHPness if
one exists.  Call the two sets of vertices in the bipartite graph of the
matrix "rows" and "columns".

Theorem:  For a bipartite graph with more rows than columns,
          the following are equivalent:
(1)  M has SHP.
(2)  There exists a maximum matching on M for which every vertex of M is
     reachable from an unmatched row vertex by an alternating path.
(3)  For every maximum matching on M, every vertex of M is reachable from
     an unmatched row vertex by an alternating path.  (I.e., any maximum
     matching will do in (2).)

Thus one can test SHP in O(e sqrt(v)) time by finding any maximum matching
and then searching along alternating paths from unmatched rows.  This also
gives a witness set if the matrix does not have SHP:  In this case the set
C' of columns not reached during the search is incident only on the set R'
of rows matched to those columns, which cannot be larger.

(Incidentally, a square matrix M is usually defined to have SHP if every
proper subset of columns is incident on a strictly larger set of rows.
Then square M has SHP iff every pair of vertices is joined by an alternating
path in some/every maximum matching.  Any bipartite graph has a canonical
"Dulmage-Mendelsohn decomposition" into subgraphs that are strong Hall or
whose transposes are strong Hall, which generalizes the strongly connected
components of a directed graph; the decomposition can be found by matching
plus depth-first search through alternating paths.)

- John Gilbert
  gilbert@parc.xerox.com