<p>The slides <a href="https://people.maths.bris.ac.uk/~csxam/presentations/matchings.pdf" rel="nofollow noreferrer">here</a> provide a way to get a pfaffian orientation from Minimum Spanning Tree. </p>

<p>MST can be found in <a href="http://www.ams.org/mathscinet-getitem?mr=1279413" rel="nofollow noreferrer">linear time</a> if graph is planar and weights are $1$ and the slides give a linear time orientation algorithm. </p>

<blockquote>
  <p>Is it possible to compute the determinant also in linear time? </p>
</blockquote>

<p>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?</p>

<hr>

<p>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?</p>

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

<hr>

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

<ul>
<li><p>First of all $\#$ of perfect matchings can be written down in $O(n)$ bits for planar graphs.</p></li>
<li><p>Secondly given adjacency matrix $A$ we can find MST in linear time for planar graphs.</p></li>
<li><p>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$).</p></li>
</ul>

<p>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.</p>

<p>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)$.</p>

CC BY-SA 3.0
2017-07-02T18:30:00.513Z
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
CC BY-SA 3.0
2017-07-02T18:36:40.423Z
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 http://web.eecs.umich.edu/~pettie/matching/Mucha-Sankowski-planar-matching-journal-version.pdf, but maybe there is some follow up work I am not aware of
Sasho Nikolov
CC BY-SA 3.0
2017-07-03T13:38:14.710Z
@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
CC BY-SA 3.0
2017-07-03T14:11:52.733Z
@JoshuaGrochow I think I made the questions so that this focusses on planarity and the other sparsity.
Turbo
CC BY-SA 4.0
2020-06-29T01:10:16.223Z
@SashoNikolov What if the degree of the graph is also at most 3?
Turbo
<permanent>
On perfect matchings on planar graphs - is there a linear time deterministic algorithm?
Turbo
# On perfect matchings on planar graphs - is there a linear time deterministic algorithm?

(Asked by: username_0 on 2017-07-01)

The slides [here](https://people.maths.bris.ac.uk/~csxam/presentations/matchings.pdf) provide a way to get a pfaffian orientation from Minimum Spanning Tree.

MST can be found in [linear time](http://www.ams.org/mathscinet-getitem?mr=1279413) 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)$.

**Tags:** permanent
> **Comments:**
> **username_1**: 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.  
> **username_1**: 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 http://web.eecs.umich.edu/~pettie/matching/Mucha-Sankowski-planar-matching-journal-version.pdf, but maybe there is some follow up work I am not aware of  
> **username_2**: @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).  
> **username_0**: @JoshuaGrochow I think I made the questions so that this focusses on planarity and the other sparsity.  
> **username_0**: @SashoNikolov What if the degree of the graph is also at most 3?  

---

## 0 answers

