3
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Sasho Nikolov Jul 2 '17 at 18:30
  • 5
    $\begingroup$ 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 $\endgroup$ – Sasho Nikolov Jul 2 '17 at 18:36
  • $\begingroup$ @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). $\endgroup$ – Joshua Grochow Jul 3 '17 at 13:38
  • $\begingroup$ @JoshuaGrochow I think I made the questions so that this focusses on planarity and the other sparsity. $\endgroup$ – T.... Jul 3 '17 at 14:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.