科研之友
微信
新浪微博
Facebook
分享链接
摘要
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 analyse 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.
- 出版日期2012-9
