Path: utzoo!utgpu!news-server.csri.toronto.edu!mailrus!uwm.edu!rpi!zaphod.mps.ohio-state.edu!tut.cis.ohio-state.edu!ucbvax!GEODUCK.CS.WASHINGTON.EDU!tompa
From: tompa@GEODUCK.CS.WASHINGTON.EDU
Newsgroups: comp.theory
Subject: Re: Finding subsets of equations
Message-ID: <9006041600.AA09706@irt.watson.ibm.com>
Date: 4 Jun 90 16:00:06 GMT
Sender: daemon@ucbvax.BERKELEY.EDU
Reply-To: tompa%geoduck.cs.washington.edu@VM1.NoDak.EDU
Lines: 33

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?

Here is a polynomial time algorithm for this problem, but I'd be interested
to know if there is a more efficient one.  Construct a bipartite graph,
whose left block contains a vertex for each of the n equations, and whose
right block contains a vertex for each of the m unknowns.  Now test if this
graph has a perfect matching.  If it does not, then, by Hall's Theorem,
there is some set of k equations with at most k-1 unknowns among them, and
you are done.  (The standard perfect matching algorithms can be made to
output the set of k equations when they fail to find a perfect matching.)

Now to finish, add a new vertex u to the left block, and invoke  the
perfect matching algorithm m more times as follows:  in the ith invocation,
u is adjacent only to the ith vertex in the right block.  If any of these m
graphs fails to have a perfect matching, it must be because k equations
have exactly k unknowns among them, one of them being the one to which u is
currently adjacent (and again, the algorithm can be made to output the set
of k equations).  If all m have perfect matchings, then every set of k
equations has at least k+1 unknowns among them, for all k.

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.

Martin Tompa
tompa@cs.washington.edu