A fixed-parameter perspective on #BIS
The problem of (approximately) counting the independent sets of a bipartite graph (#BIS) is the canonical approximate counting problem that is complete in the intermediate complexity class #RHΠ1. It is believed that #BIS does not have an efficient approximation algorithm but also that it is not NP-h...
Main Authors: | , , , , |
---|---|
Format: | Journal article |
Published: |
Springer
2019
|