# On perfect matchings on planar graphs - is there a linear time deterministic algorithm?

The slides here provide a way to get a pfaffian orientation from Minimum Spanning Tree.

MST can be found in linear time if graph is planar and weights are $1$ and the slides give a linear time orientation algorithm.

Is it possible to compute the determinant also in linear time?

Note that if we explicitly write down the matrix with Pfaffian orientation we need $\Omega(|V|^2)$ space to write down the matrix. But since number of edges is only $O(|V|)$ we might be able to get away with linear time algorithm for counting number of perfect matchings of a planar graph. Is this possible?

If $M\in\{-1,0,+1\}^{n\times n}$ be a matrix with only $O(n)$ non-zero entries and hadamard product $M\odot M$ being symmetric can we compute $Det(M)$ in $O(n)$ bit complexity?

Assume that the matrix is given in form a list where $1,-1$ locations are and so the presentation is only $O(n)$ sized.

The motivation comes from possibility of counting $\#$ of perfect matchings in planar graphs in linear time?

• First of all $\#$ of perfect matchings can be written down in $O(n)$ bits for planar graphs.

• Secondly given adjacency matrix $A$ we can find MST in linear time for planar graphs.

• Thirdly from MST we can find a pfaffian orientation and find $M\in\{-1,0,+1\}^{n\times n}$ in linear time (So $M\odot M=A$).

So it seems highly plausible it should be the case that $\#$ of perfect matchings on planar graph should be computable in linear time with $O(n)$ bit complexity.

However if we use $Det(M)$ directly we cannot avoid $O(n^2)$ at best. But there may be an indirect way to compute $Det(M)$.

• Any spanning tree is an MST if you have all weights equal to 1. A spanning tree can be computed in linear time on any graph using BFS/DFS. – Sasho Nikolov Jul 2 '17 at 18:30
• I don't think it's known even how to decide if there exists a perfect matching in a planar graph in linear time. The fastest algorithm I know of is web.eecs.umich.edu/~pettie/matching/…, but maybe there is some follow up work I am not aware of – Sasho Nikolov Jul 2 '17 at 18:36
• @Turbo: Rather than duplicating the question here about determinants, better to just put a link to the other question (and the other question could also link here). – Joshua Grochow Jul 3 '17 at 13:38
• @JoshuaGrochow I think I made the questions so that this focusses on planarity and the other sparsity. – 1.. Jul 3 '17 at 14:11
• @SashoNikolov What if the degree of the graph is also at most 3? – 1.. Jun 29 at 1:10