Algorithm to find all (up to isomorphism) perfect matchings of quartic plane graphs

Question

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.

Answer 1

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).

Answer 2

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

Answer 3

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.

Answer 4

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.

Answer 5

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).

Answer 6

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.