Path: utzoo!attcan!uunet!tut.cis.ohio-state.edu!ucbvax!CS.PSU.EDU!furer From: furer@CS.PSU.EDU (Martin Furer) Newsgroups: comp.theory Subject: Re: Finding subsets of equations Message-ID: <9006051457.AA12156@irt.watson.ibm.com> Date: 5 Jun 90 14:57:19 GMT Sender: daemon@ucbvax.BERKELEY.EDU Reply-To: Martin Furer Lines: 43 Russell J. Abbott has asked: > 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 has answered with a polynomial time algorithm calling a maximum bipartite matching subroutine m+1 times. He has remarked: > 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. In fact Martin Tompa's implicit conjecture is correct, one call to a matching algorithm is sufficient. First, we follow Martin Tompa. We form the bipartite graph with equations on the left and unknowns on the right hand side, and we compute a maximum matching. If the maximum matching does not involve all equations (i.e., it is not left-"perfect"), then the standard algorithm gives a subset of vertices violating Hall's condition and solving the problem. Now, let us look at the case, where every left vertex (equation) is matched. We transform the bipartite graph into a directed graph as follows. We direct all edges from left to right. In addition, the matched edges are directed from right to left too. Using depth-first search, we compute the strongly connected components of this directed graph. These components are partially ordered by: component(u) < component(v) iff there is a directed path from u to v. Take any anti-chain (i.e., set of incomparable components) in this partial order, and add all components which are greater (with respect to < ) than any component in the anti-chain. We have a perfect matching on this subset, and there is no edge to a right vertex (an unknown) outside. Hence, this is a solution to the problem. In fact, it is not hard to see that every solution is of this form (in the case, where a left-"perfect" matching exists). Martin Furer Pennsylvania State University furer@shire.cs.psu.edu