1
$\begingroup$

We can find Pfaffian orientation and take determinant to compute permanent in $O(n^\omega)$ time where $\omega$ is exponent of matrix multiplication.

We know that permanent of $O(n)$ vertex planar graphs cannot exceed $2^{O(n)}$.

So perhaps there are classes of graphs whose permanent can be computed in linear time.

What classes of planar graphs can number of perfect matchings be computed in linear time?

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ Your question is difficult to parse and somewhat unclear ... but considering that cubic graphs (planar or otherwise) have exponentially many perfect matchings with respect to the order of the graph, you might want to consider graphs like even circuits, disjoint unions of $K_2$’s, etc. Even a disjoint union of even circuits will get a lot of perfect matchings if you have a lot of components: say you have n squares (that is 4n vertices). Then you already have $2^n$ perfect matchings. $\endgroup$
    – EGME
    Commented Jun 25, 2019 at 19:31
  • $\begingroup$ @EGME Those are interesting suggestions. $\endgroup$
    – Turbo
    Commented Jun 25, 2019 at 20:15

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .