Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

I need to find all (up to isomorphism) perfect matchings of some quartic plane graphs. I haven't found any specific algorithm to give me all the perfect matchings. Does anybody know about such an algorithm or any results that could be useful when implementing such an algorithm? At the moment I can only think of a branch-and-bound approach.

I don't really expect there to be an algorithm for this specific case, but I thought I'd mention all properties of the graphs. Maybe there are results for plane graphs, planar graphs or quartic graphs.

share|improve this question
1  
en.wikipedia.org/wiki/FKT_algorithm is polynomial time for counting perfect matchings in a planar graph. Is this enough? –  John Wiltshire-Gordon Feb 28 '12 at 18:24
    
I had found that article as well, but I'm afraid I really need to have the different matchings. –  nvcleemp Feb 28 '12 at 18:50
1  
How big are the problems you care about? Small cases can presumably be solved by brute force, and large cases may have impossibly large numbers of matchings, so the real question is whether you are somewhere in between. –  Henry Cohn Feb 28 '12 at 19:07
    
The goal is an exhaustive generation for small cases. I will need to go as far as possible, so maybe a bit smarter than brute-force. Basically I'm just trying to explore whether something better than bruteforce is possible. –  nvcleemp Feb 28 '12 at 21:43
add comment

6 Answers

up vote 4 down vote accepted

OK, here is a way which uses my other answer:

  • Number the edges of your graph in some order.
  • Check if your graph $G$ has a perfect matching.
  • If no, return $\emptyset.$
  • Add the lowest number edge to the matching, delete the edges incident to the endpoints. Call the resulting graph $G^\prime.$
  • Recursively, return all the matchings in $G^\prime$ (union the first edge).
  • Now, use the second lowest-numbered edge as the first edge.
  • Halt when the total number of edges left is smaller than half the number of vertices.

Note that this algorithm (using the algorithms referenced in my other answer) will run in something like $n^{3/2}$ times the number of actual perfect matchings, which is pretty good. Those who care about such things will recognize the algorithm as a simple backtracking algorithm (as used in e.g. the $N$-queens problem).

share|improve this answer
    
Thanks, that would have been more or less the approach I would have taken. I only would have started four times from an edges around an arbitrary vertex, since at least one of these needs to be in the perfect matching. I was mostly looking for result which would allow me to efficiently bound the generation. I think that complexity is sufficient for now. I can come back later and try to eliminate some matchings if it turns out that certain matching don't agree with the geometrical restriction later on in the generation. –  nvcleemp Feb 29 '12 at 6:27
    
If there are two edges splitting the graph into approxiomately equal halves then they should be examined first. As I comment below, you can make choices as you go in your search to be more efficient. –  Aaron Meyerowitz Feb 29 '12 at 8:26
add comment

This is a very easy problem for the sizes you are proposing... a 20-vertex quartic graph seems to only have a few hundred perfect matchings (random sample), and it takes my computer approximately 2/100ths of a second to count them.

This is actually an ideal application for my favourite constraint satisfaction programming solver, namely Minion. It took me 15 minutes to write and test a program that converts a graph into a suitable Minion program, and then the Minion program takes the above-mentioned 2/100ths of a second.

I used to write lots of back-tracking programs, but Minion is so good that for almost all applications, it beats a bespoke program by a wide margin, and so nowadays I almost never write my own back-track, but just convert to a Minion program!

Here's an example of the Minion program for a 20-vertex graph - there are 40 boolean variables, one for each edge, stored in an array called "ed". The line "sumgeq(ed,10)" says that we need the sum of the 40 variables in the array to be at least 10 (in fact we want exactly 10, but in a strange decision, Minion only allows you to specify equality as a combination of two inequalities). Then for each VERTEX, we need exactly one edge to be chosen, and so we have 40 constraints in 20 pairs, with each pair saying that "at least one", and "at most one", of the edges incident with a particular vertex is chosen.

Running this code then takes a few hundredths of a second and produces the answer that there are exactly 364 perfect matchings.

MINION 3
**VARIABLES**
BOOL ed[40]
**CONSTRAINTS**
sumgeq(ed,10)
sumleq([ed[0],ed[1],ed[2],ed[3]],1)
sumleq([ed[4],ed[5],ed[6],ed[7]],1)
sumleq([ed[8],ed[9],ed[10],ed[11]],1)
sumleq([ed[8],ed[12],ed[13],ed[14]],1)
sumleq([ed[0],ed[9],ed[15],ed[16]],1)
sumleq([ed[15],ed[17],ed[18],ed[19]],1)
sumleq([ed[16],ed[20],ed[21],ed[22]],1)
sumleq([ed[4],ed[23],ed[24],ed[25]],1)
sumleq([ed[1],ed[12],ed[17],ed[23]],1)
sumleq([ed[2],ed[20],ed[26],ed[27]],1)
sumleq([ed[13],ed[26],ed[28],ed[29]],1)
sumleq([ed[24],ed[30],ed[31],ed[32]],1)
sumleq([ed[10],ed[30],ed[33],ed[34]],1)
sumleq([ed[5],ed[33],ed[35],ed[36]],1)
sumleq([ed[18],ed[28],ed[31],ed[37]],1)
sumleq([ed[14],ed[25],ed[37],ed[38]],1)
sumleq([ed[6],ed[19],ed[21],ed[39]],1)
sumleq([ed[11],ed[27],ed[29],ed[35]],1)
sumleq([ed[3],ed[7],ed[22],ed[39]],1)
sumleq([ed[32],ed[34],ed[36],ed[38]],1)
sumgeq([ed[0],ed[1],ed[2],ed[3]],1)
sumgeq([ed[4],ed[5],ed[6],ed[7]],1)
sumgeq([ed[8],ed[9],ed[10],ed[11]],1)
sumgeq([ed[8],ed[12],ed[13],ed[14]],1)
sumgeq([ed[0],ed[9],ed[15],ed[16]],1)
sumgeq([ed[15],ed[17],ed[18],ed[19]],1)
sumgeq([ed[16],ed[20],ed[21],ed[22]],1)
sumgeq([ed[4],ed[23],ed[24],ed[25]],1)
sumgeq([ed[1],ed[12],ed[17],ed[23]],1)
sumgeq([ed[2],ed[20],ed[26],ed[27]],1)
sumgeq([ed[13],ed[26],ed[28],ed[29]],1)
sumgeq([ed[24],ed[30],ed[31],ed[32]],1)
sumgeq([ed[10],ed[30],ed[33],ed[34]],1)
sumgeq([ed[5],ed[33],ed[35],ed[36]],1)
sumgeq([ed[18],ed[28],ed[31],ed[37]],1)
sumgeq([ed[14],ed[25],ed[37],ed[38]],1)
sumgeq([ed[6],ed[19],ed[21],ed[39]],1)
sumgeq([ed[11],ed[27],ed[29],ed[35]],1)
sumgeq([ed[3],ed[7],ed[22],ed[39]],1)
sumgeq([ed[32],ed[34],ed[36],ed[38]],1)
**EOF**
share|improve this answer
    
This is a really useful answer. I wasn't aware of Minion, and it seems like a much better approach (in most cases) than writing custom programs. –  Henry Cohn Mar 1 '12 at 1:22
    
That's very cool... –  Igor Rivin Mar 1 '12 at 15:00
add comment

The answer which is useful to you may depend on the details, so it would be good to have more. You mention isomorphism, quartic (regular of degree 4) and planar. Each of these could be important or ignored.

"Up to isomorphism"

  • The jokey answer is that all graphs with $v/2$ disjoint edges are isomorphic so you just have to find if you have one! But that isn't what you mean.
  • If you know some automorphisms that could speed things up quite a bit. You might be able to efficiently list all the matching types for antiprisms up to a large size. ditto for the two kinds of prisms with a cupola on each end.
  • If you need to discover the automorphism group of a 14-30 vertex graph then there are various packages to do that but it is a big discussion.
  • I'll just consider listing all the perfect matchings without worrying about isomorphism.

"Planar" There are various decompositions for planar graphs which can speed calculations.

  • If it happens that your graph is made of two or more disjoint connected components then you have to find all the perfect matchings for each piece and then you can say "take one from column A, one from column B and one from column C" (or actually do it.)

  • Of course you may have only connected graphs, but if your graph has a bridge then you can decide not to use it and do what was described above and then also decide to use it , remove the endpoints and do as above.

  • Actually, only one (at most) of those two things will leave an even number of unmatched vertices on each half so that is all you have to do.

  • There are fast algorithms to find all the bridges (giving a tree like structure) and all the cutpoints

  • other decompositions might identify 3-connected blocks joined by a pair of edges or even more exotic things. This could be overkill for 20 vertices. But if a cutset of $j$ edges is found then one has $2^j$ ways to split into a pair of simpler problems. If $j$ is small, the sub-problems have about half the number of vertices and several of the sub-problems can be discarded as infeasible, this can be quite effective.

4-regular Maybe there are theorems about such beasts although after a partial matching you are stuck with one or more graphs with degrees at most 4.

Exact Cover Without explicitly saying anything about being planar or 4-regular or even a graph, perfect matching is a special case of the exact cover problem (as are sudoku, n-queens and many other problems). Even if you are going to do an exhaustive search there are more and less clever ways to do it. the dancing links algorithm of Donald Knuth is a depth first search using doubly linked circular lists for very efficient backtracking . It can be set to choose each step as one which may be most productive (if a vertex only has one edge on it, put that in the matching before doing anything else, etc.)

Of course if a sub-problem has an odd number of vertices then it is time to backtrack, there may be productive preprocessing such as the decompositions above.

share|improve this answer
1  
The dancing links is also very efficient for parallel implementation. –  Aaron Meyerowitz Feb 29 '12 at 8:52
add comment

This paper (maximum matching in planar graphs using Gaussian Elmination, by Mucha-Sankowski, J. Algorithms 2006) shows how to generate matchings uniformly at random, which, for a graph of any reasonable size is far more useful than generating all the matching (which, as Henry points out, is not useful once the size of the graph is bigger than a couple of dozen).

share|improve this answer
    
I'm sorry, but for my application I really need all matchings. I doubt it I will go much further than 20 vertices at this stage. –  nvcleemp Feb 28 '12 at 21:45
1  
Would you mind sharing WHY you need all the matchings? –  Igor Rivin Feb 28 '12 at 22:35
    
I'm writing a generator for a certain type of spherical tilings by quadrangulations. We found a reduction where each perfect matching of the dual graph leads to a whole set of such tilings. I'm now trying to implement this algorithm to obtain testing data. –  nvcleemp Feb 29 '12 at 6:20
2  
OK, fair enough, though I am guessing that generating random matching would be quite useful for you as well (and you could try it with much bigger graphs...) –  Igor Rivin Feb 29 '12 at 14:46
add comment

I'll just address the "up to isomorphism" requirement, assuming you have an algorithm for making all the perfect matchings. I'm assuming you are only consider embedding-preserving automorphisms. A connected plane graph with $m$ edges has at most $4m$ embedding-preserving automorphisms, and in most interesting classes (such a quartic graphs) most graphs have only the trivial automorphism. Make a complete list of automorphisms by starting a BFS (or DFS) scan starting at each flag. Then for each perfect matching $M$, reject it if there an automorphism $g$ such that $g(M)$ is lexicographically less than $M$. Since most graphs except very small ones have only the identity automorphism, the overall cost of this is approximately zero. For the same reason, it is a waste of time to consider the automorphisms during the perfect matching generation, unless you are working on a class of graphs where automorphisms are common.

share|improve this answer
add comment

I want to mention that you can exploit your favorite symbolic algebra package to do this job for smallish graphs. I've used this method successfully for graphs with 20-30 vertices.

The FKT algorithm expresses the number of matchings of a planar graph as a pfaffian, where each nonzero entry of the matrix is $\pm 1$, corresponding to an edge $e$ of the graph. Write down the same matrix but replace $\pm 1$ by $\pm x(e)$, where $x(e)$ is a formal variable corresponding to the edge $e$, and ask your favorite computer algebra package to take the determinant. The result will be $\sum_M \prod_{e \in M} x(e)$, where the sum is over all matchings $M$. So you can look at the output and immediately read off your matchings.

This is most useful when the graph is bipartite, as the Pfaffian then simplifies to a determinant, and where the graph is small and/or symmetric enough to carry out the orientation part of the algorithm by hand.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.