Approximately counting bases of bicircular matroids

Abstract

We give a fully polynomial-time randomised approximation scheme (FPRAS) for the number of bases in a 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.

v3: updated introduction and a slightly better run-time bound. v4: minor revisions; this version is accepted for publication in Combinatorics, Probability and Computing (CPC)

References in corpus (4)

• Elementary bounds on Poincare and log-Sobolev constants for decomposable Markov chains
• A polynomial-time approximation algorithm for all-terminal network reliability
• A Faster Approximation Algorithm for the Gibbs Partition Function
• Tight bounds for popping algorithms

Cited by in corpus (4)

• Perfect sampling from spatial mixing
• Fundamentals of Partial Rejection Sampling
• Moser-Tardos Algorithm: Beyond Shearer's Bound
• On Cyclic Matroids and their Applications