  Jerrum, Sinclair and Vigoda (2004) showed that the permanent of any square
matrix can be estimated in polynomial time. This computation can be viewed as
approximating the partition function of edge-weighted matchings in a bipartite
graph. Equivalently, this may be viewed as approximating the partition function
of vertex-weighted independent sets in the line graph of a bipartite graph.
Line graphs of bipartite graphs are perfect graphs, and are known to be
precisely the class of (claw, diamond, odd hole)-free graphs. So how far does
the result of Jerrum, Sinclair and Vigoda extend? We first show that it extends
to (claw, odd hole)-free graphs, and then show that it extends to the even
larger class of (fork, odd hole)-free graphs. Our techniques are based on graph
decompositions, which have been the focus of much recent work in structural
graph theory, and on structural results of Chvatal and Sbihi (1988), Maffray
and Reed (1999) and Lozin and Milanic (2008).
