Path: utzoo!attcan!uunet!cs.utexas.edu!usc!zaphod.mps.ohio-state.edu!rpi!turing.cs.rpi.edu!spencert
From: spencert@turing.cs.rpi.edu (Thomas Spencer)
Newsgroups: comp.theory
Subject: Re: Finding subsets of equations
Message-ID: <`B~$LZ|@rpi.edu>
Date: 4 Jun 90 20:16:22 GMT
References: <9006041600.AA09706@irt.watson.ibm.com>
Reply-To: spencert@turing.cs.rpi.edu (Thomas Spencer)
Organization: RPI CS Dept.
Lines: 79

In article <9006041600.AA09706@irt.watson.ibm.com> tompa%geoduck.cs.washington.edu@VM1.NoDak.EDU writes:
>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



Only one call to the maximum cardinality matching algorithm is necessary.
First, find a maximum cardinality matching M.  If it does not match all of 
the equations, we're done, as Martin says.  Next, direct all of the edges
not in M, from the unknown to the equation and all the edges in M from
the equation to the unknown.  Finally, determine if there is a directed
path to each equation from some unmatched unknown.  (This is the same
thing as determining if every equation is reachable via an alternating
path from an unmatched unknown.)  If every equation is reachable, then
no such set exists; otherwise, the unreachable equations are the desired 
set.

To see why this is true, let's consider the case where the set of unreachable
equations is empty, first.  Consider a set S, of equations.  It is adjacent,
via edges in the matching to a set T of unknowns.  It is enough to show
that it is also adjacent to some other unknown.  Consider an equation r
in S.  There is a path P from some unmatched unknown u to r.  Let v be
the first equation in S on this path, and let w be the previous unknown
along this path.  w is either the first vertex of the path P, or the 
edge of P entering w is matched.  In either case w can not be in T, but
w is adjacent to S.  Thus, the equations in S contain more unknowns than
the number of equations in S.

Conversely, the set of unreachable equations might not be empty.  Call 
this set S.  Let T be the set of unknowns adjacent to S.  Suppose that 
T contains an unknown x that is not matched to an equation in S.  Since
x is in T, x is adjacent to some equation y in S.  If x is not matched 
at all, then y is reachable, contrary to the definition of S.  Alternatively, 
x may be matched to some vertex z not in S.  But, z is reachable and the
path can be extended through x to y.  Again this contradicts the definition
of S.  Therefore, T contains only unknowns that are matched to equations
in S, so |T| <= |S|.  QED

I hope that this helps





			-Tom Spencer
			 spencert@turing.cs.rpi.edu
			 uunet!steinmetz!itsgw!spencert
"First figure out what you are trying to do."  -Me.