http://qs1969.pair.com?node_id=600482

in reply to decomposing binary matrices

As I suggested in the CB, if your ultimate goal is only to find an assignment of values to variables that meets all the constraints, then you don't have to actually decompose the matrix. All you need to do is find a perfect bipartite matching.

A bipartite graph is a graph where the vertices are partitioned into 2 sets, and every edge crosses between these sets (i.e, does not stay within a set). In this case, one set denotes your variables and the other set denotes your values. Draw an edge between a variable and a value if it is legal to assign that value to that variable.

A matching is a subset of edges from a graph, where no two edges share an endpoint. Since all edges in a bipartite graph run between these 2 sets, you can think of a matching as a (partial) mapping from 1 set to the other (each vertex in set A is paired with at most 1 vertex in set B). In this case, it represents a mapping from variables to values. Since the matching is a subset of the available edges, the mapping doesn't include any assignments that you have deemed "illegal".

What you want is a perfect matching, one that covers all vertices (so it's a 1-to-1 mapping between variables and values). Usually this problem is phrased as the "marriage problem" -- The two sets of vertices are men & women, and there is an edge between a man & a woman if they could be happy married. You want to know if there is a way to pair them up so that each couple is happy (and if there is such a way to pair them up, output it).

An example that I found with pictures is here: bipartite matching. Googling for bipartite matching algorithm turns up plenty of hits. I know that there are efficient algorithms for doing it, but can't remember all of the details.

Replies are listed 'Best First'.
Re^2: decomposing binary matrices
by hv (Parson) on Feb 16, 2007 at 17:37 UTC

Thanks, these are useful terms and concepts for me.

I'm not looking for a perfect match - that would correspond to "a possible assignment". I'm looking for information encapsulating the set of all perfect matches.

One interpretation of that is that if I represent the 5x5 matrix of my OP as a bipartite graph, I'm looking for the edges that are missing from every perfect match, since I can delete them. Deleting those edges would effectively split the graph into connected subgraphs (corresponding to the 2x2 and 3x3 submatrices in the OP).

In short, I'm looking to use the constraint "each variable has a distinct value" to reduce the number of 1s in the matrix.

In practice, I think it would simplify visualisation and make further work more efficient if the resulting discrete subgraphs/submatrices were separated, but I do not think that is in principle necessary - the job is to maximise the information extracted from the constraint. In the example, the constraint tells me that each of the assignments C=2, D=2, B=4 is impossible in any perfect match, so those three 1s in the matrix can be zeroed, or those three edges in the graph can be deleted. Each of the remaining edges can appear in some perfect match, so that's the sum of the information derivable from that constraint at this point.

Update: I should add that in some cases the number of possible values will be greater than the number of variables. In that case, a "perfect match" for the above argument would be a 2n-node cycle that covers each of the n variables: inevitably, some of the values would be left out in any one such match.

Hugo

Re^2: decomposing binary matrices
by hv (Parson) on Feb 17, 2007 at 13:30 UTC

Thinking about this further last night, I can refine the requirement to finding: that union of cyclic alternating paths which puts each node in the longest possible cycle. This page you referenced uses the discovery of alternating paths at the core of its algorithm - I need to analyse it further to see if it can be extended to discern the longest cycles.

I was perhaps overly swayed by reading that the problem of "finding the longest cycle" is NP-hard - that is for a general graph, and it seems entirely possible that the special case of a bipartite graph introduces enough structure to make it rather easier.

Hugo