Paper Info
Title
A graph polynomial for independent sets of bipartite graphs
Abstract
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.
Year
DOI
Venue
2012
10.1017/S0963548312000296
Foundations of Software Technology and Theoretical Computer Science
Keywords
DocType
Volume
dichotomy result,points exact evaluation,rational point,bipartite graph,perfect matchings,new graph polynomial,exact evaluation,interesting property,independent set,generalized riemann hypothesis
Journal
21
Issue
ISSN
Citations 
5
0963-5483
6
PageRank 
References 
Authors
0.51
33
2
Name
Order
Citations
PageRank
Qi Ge1282.01
Daniel Stefankovic224328.65