Conference item icon

Conference item

A fixed-parameter perspective on #BIS

Abstract:

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-hard. We study the robustness of the intermediate complexity of #BIS by considering variants of the problem parameterised by the size of the independent set. We exhaustively map the complexity lands...

Expand abstract
Publication status:
Published
Peer review status:
Peer reviewed
Version:
Publisher's version

Actions


Access Document


Files:
Publisher copy:
10.4230/LIPIcs.IPEC.2017.13

Authors


More by this author
Department:
Oxford, MPLS, Computer Science
Role:
Author
More by this author
Department:
Oxford, MPLS, Computer Science
Role:
Author
Publisher:
Schloss Dagstuhl Publisher's website
Volume:
89
Pages:
13:1--13:13
Series:
Leibniz International Proceedings in Informatics
Publication date:
2018-02-23
Acceptance date:
2017-07-25
DOI:
ISSN:
1868-8969
Pubs id:
pubs:718347
URN:
uri:e2315fcf-9778-4f77-aa5b-c645e0917b12
UUID:
uuid:e2315fcf-9778-4f77-aa5b-c645e0917b12
Local pid:
pubs:718347
ISBN:
978-3-95977-051-4

Terms of use


Metrics


Views and Downloads






If you are the owner of this record, you can report an update to it here: Report update to this record

TO TOP