A graph polynomial for independent sets of bipartite graphs

Qi Ge & Daniel Stefankovic
We introduce a new graph polynomial that encodes interesting properties of graphs, for example, the number of matchings, the number of perfect matchings, and, for bipartite graphs, the number of independent sets (#BIS). We analyze the complexity of exact evaluation of the polynomial at rational points and show a dichotomy result---for most points exact evaluation is #P-hard (assuming the generalized Riemann hypothesis) and for the rest of the points exact evaluation is trivial. We propose...
This data repository is not currently reporting usage information. For information on how your repository can submit usage information, please see our documentation.