Curticapean, Radu ;
Dell, Holger ;
Fomin, Fedor V. ;
Goldberg, Leslie Ann ;
Lapinskas, John
A FixedParameter 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 #RHPi_1. It is believed that #BIS does not have an efficient approximation algorithm but also that it is not NPhard. 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 map the complexity landscape for three problems, with respect to exact computation and approximation and with respect to conventional and parameterised complexity. The three problems are counting independent sets of a given size, counting independent sets with a given number of vertices in one vertex class and counting maximum independent sets amongst those with a given number of vertices in one vertex class. Among other things, we show that all of these problems are NPhard to approximate within any polynomial ratio. (This is surprising because the corresponding problems without the size parameter are complete in #RHPi_1, and hence are not believed to be NPhard.) We also show that the first problem is #W[1]hard to solve exactly but admits an FPTRAS, whereas the other two are W[1]hard to approximate even within any polynomial ratio. Finally, we show that, when restricted to graphs of bounded degree, all three problems have efficient exact fixedparameter algorithms.
BibTeX  Entry
@InProceedings{curticapean_et_al:LIPIcs:2018:8561,
author = {Radu Curticapean and Holger Dell and Fedor V. Fomin and Leslie Ann Goldberg and John Lapinskas},
title = {{A FixedParameter Perspective on #BIS}},
booktitle = {12th International Symposium on Parameterized and Exact Computation (IPEC 2017)},
pages = {13:113:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770514},
ISSN = {18688969},
year = {2018},
volume = {89},
editor = {Daniel Lokshtanov and Naomi Nishimura},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/8561},
URN = {urn:nbn:de:0030drops85613},
doi = {10.4230/LIPIcs.IPEC.2017.13},
annote = {Keywords: Approximate counting, parameterised complexity, independent sets}
}
02.03.2018
Keywords: 

Approximate counting, parameterised complexity, independent sets 
Seminar: 

12th International Symposium on Parameterized and Exact Computation (IPEC 2017)

Issue date: 

2018 
Date of publication: 

02.03.2018 