Permanent mod $2$ of biadjacency gives polynomial time algorithm of $\#PM(G)\mod 2$ of perfect matchings of bipartite graph. Is there a similar efficient strategy for general graphs?
$\begingroup$
$\endgroup$
6
-
2$\begingroup$ Same formula, via the Pfaffian mod 2? en.wikipedia.org/wiki/Pfaffian $\endgroup$– Noam D. ElkiesCommented Jul 12, 2019 at 22:59
-
$\begingroup$ @NoamD.Elkies Thank you but link references planar graphs. $\endgroup$– TurboCommented Jul 12, 2019 at 23:31
-
2$\begingroup$ The Hafnian <en.wikipedia.org/wiki/Hafnian> is congruent mod 2 to the Pfaffian (same terms but no +/- signs) and gives the number of matchings in general, as the permanent does for a bipartite graph (and indeed the permanent and determinant are likewise congruent mod 2). The special property of planar graphs is that the +/- signs are all the same so the Pfaffian gives the actual number, not just the parity. $\endgroup$– Noam D. ElkiesCommented Jul 13, 2019 at 0:15
-
$\begingroup$ @NoamD.Elkies Since I do not know I want to clarify. It seems $Pf(A)^2=det(A)$ for skew-symmetric $A$ and since signs are removed here $A$ is not skew-symmetric. However $\mod 2$ signs do not matter. So just $det(A)\bmod 2$ gives necessary $\#PM(G)\bmod 2$ of graph $G$ whose adjacency is $A$? $\endgroup$– TurboCommented Jul 13, 2019 at 13:40
-
3$\begingroup$ Are you asking about the number of perfect matchings modulo $2$ ? Because in that case, as @NoamD.Elkies suggested, that number (or, rather, a number congruent to it modulo $2$) can be computed as the Pfaffian of the skew adjacency matrix (= the result of replacing all $1$s by $-1$s below the diagonal of the adjacency matrix) of the graph. Thus, it can also be computed as the determinant of this matrix (in fact, the determinant is the square of the Pfaffian, and therefore congruent to the Pfaffian modulo $2$). See Theorem 12.81 in Nicholas Loehr, Bijective Combinatorics, 1st edition 2011. $\endgroup$– darij grinbergCommented Jul 15, 2019 at 19:39
|
Show 1 more comment