Hosoya index
Algorithms

The Hosoya index is #P-complete to compute, even for planar graphs. However, it may be calculated by evaluating the matching polynomial m at the argument 1. Based on this evaluation, the calculation of the Hosoya index is fixed-parameter tractable for graphs of bounded treewidth and polynomial (with an exponent that depends linearly on the width) for graphs of bounded clique-width. The Hosoya index can be efficiently approximated to any desired constant approximation ratio using a fully-polynomial randomized approximation scheme.
oulipo:avoid_letter[o]