linguistic:voice_change, information:highlighting
Computational complexity

On arbitrary graphs, or even planar graphs, computing the matching polynomial is #P-complete (Jerrum 1987). However, it can be computed more efficiently when additional structure about the graph is known. In particular,computing the matching polynomial on n -vertex graphs of treewidth k is fixed-parameter tractable: there exists an algorithm whose running time, for any fixed constant k, is a polynomial in n with an exponent that does not depend on k (Courcelle, Makowsky & Rotics 2001).The matching polynomial of a graph with n vertices and clique-width k may be computed in time n (Makowsky et al. 2006).