We give a fully polynomial-time randomised approximation scheme (FPRAS) for the number of bases in bicircular matroids. This is a natural class of matroids for which counting bases exactly is #P-hard and yet approximate counting can be done efficiently.
|Pages (from-to)||124 - 135|
|Number of pages||12|
|Journal||Combinatorics, Probability and Computing|
|Early online date||6 Aug 2020|
|Publication status||Published - 1 Jan 2021|