Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!uunet!mcsun!ukc!strath-cs!cs.glasgow.ac.uk!rwi
From: rwi@cs.glasgow.ac.uk (Dr Rob Irving)
Newsgroups: comp.theory
Subject: Re: Finding subsets of equations
Summary: Using bipartite matching to find subsets of equations with at least as
	 many equations as unknowns
Message-ID: <5392@vanuata.cs.glasgow.ac.uk>
Date: 4 Jun 90 10:17:36 GMT
References: <74444@aerospace.AERO.ORG>
Organization: Computing Sci, Glasgow Univ, Scotland
Lines: 36

In article <74444@aerospace.AERO.ORG>, abbott@aerospace.aero.org (Russell J. Abbott) writes:

> 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?


It can be solved using bipartite matching as follows:

Construct a bipartite graph G with one set of vertices W representing the
equations and the other set U representing the unknowns. Join a vertex w in W to
a vertex u in U if the equation w contains the unknown x.

By matching theory, there is a set of q equations involving <q unknowns if and
only if the maximum cardinality matching in G has <q edges. Applying a bipartite
matching algorithm, such as the standard one based on augmenting paths, will
therefore determine whether such a set of equations exists, and if so, can
easily be extended to find a 'critical' set  -  i.e., a smallest such set
with maximum excess of equations over unknowns (maximum 'deficiency' in the
terminology of matching).

Otherwise, if there is a set of q equations involving exactly q unknowns,
first find a maximum cardinality matching M in G; say it involves vertices
(unknowns) x_1, ..., x_n. Then for each of these vertices in turn, remove it
from G and find a maximum cardinality matching in the resulting graph. As soon
as the resulting matching has size n-1 (rather than n) then the corresponding
critical set of equations is the one (or at least one of those) sought.

Since bipartite matching can be solved in O(|E||V|^0.5) time, where V is the
vertex set and E the edge set, this method is clearly much better than
exhaustive search.

Rob Irving.