A Graph Polynomial for Independent Sets of Bipartite Graphs

被引：7

作者：

Ge, Q. ^{[1
]}

Stefankovic, D. ^{[1
]}

机构：

[1] Univ Rochester, Dept Comp Sci, Rochester, NY 14627 USA

来源：

COMBINATORICS PROBABILITY & COMPUTING | 2012年 / 21卷 / 05期

基金：

美国国家科学基金会;

关键词：

COMPUTATIONAL-COMPLEXITY; SPARSE;

D O I：

10.1017/S0963548312000296

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

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.

引用

页码：695 / 714

页数：20

共 36 条

[1]

[Anonymous], FDN COMPUTING SERIES

[2] A two-variable interlace polynomial [J].