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: | Conference item |
| Published: |
Schloss Dagstuhl
2018
|