3
$\begingroup$

Determinant modulo $2$ of biadjacency matrix of bipartite graphs provide mod $2$ information on number of perfect matchings on bipartite graphs providing polynomial complexity in bipartite situations.

Is there a similar trick for general graphs which is in polynomial complexity?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
4
$\begingroup$

One can use Pfaffians of the adjacency matrix. It will look like

$\text{pf}(A) = \sum_{\sigma} \text{sgn}(\sigma) \cdot (\text{product of n entries of A})$

over certain permutations where the product is 1 if and only those $n$ edges make a perfect matching. Hence, we sum $\pm 1$ for each matching and obtain the count $\pmod 2$.

This idea can be used to try to exactly count perfect matching by weighting the entries of the adjacency matrix. This can be done by finding a Pfaffian orientation (also called a Kasteleyn orientation). Such on orientation can be found efficiently for planar graphs using the FKT algorithm.

Edit addition: To answer original question more specifically. Yes, we can do this polynomial time. One way is arbitrarily oriented the graph so the adjacency matrix is skew-symmetric. Then $\text{pf}(A)^2 = \det(A)$. So, $\text{pf}(A)$ and $\det(A)$ have the same parity and we can compute will Gaussian elimination efficiently.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Is it in polynomial time? $\endgroup$
    – Turbo
    Commented Nov 18, 2020 at 6:28
  • $\begingroup$ Yes, we can get the parity in polynomial time. I added a bit about this to the answer to be more explicit to your question. $\endgroup$
    – John Machacek
    Commented Nov 18, 2020 at 18:51

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .