Approximate Counting of Matchings in $(3,3)$-Hypergraphs
Preprint
Abstract
We design a fully polynomial time approximation scheme (FPTAS) for counting the number of matchings (packings) in arbitrary 3-uniform hypergraphs of maximum degree three, referred to as $(3,3)$-hypergraphs. It is the first polynomial time approximation scheme for that problem, which includes also, as a special case, the 3D Matching counting problem for 3-partite $(3,3)$-hypergraphs. The proof technique of this paper uses the general correlation decay technique and a new combinatorial analysis of the underlying structures of the intersection graphs. The proof method could be also of independent interest.Keywords
All Related Versions
This publication has 11 references indexed in Scilit:
- The Computational Hardness of Counting in Two-Spin Models on d-Regular Graphs2012
- The roots of the independence polynomial of a clawfree graphJournal of Combinatorial Theory, Series B, 2007
- On Counting Independent Sets in Sparse GraphsSIAM Journal on Computing, 2002
- The complexity of counting colourings and independent sets in sparse graphs and hypergraphscomputational complexity, 2000
- Fast convergence of the Glauber dynamics for sampling independent setsRandom Structures & Algorithms, 1999
- Approximating the PermanentSIAM Journal on Computing, 1989
- Stochastic Models of Computer Communication SystemsJournal of the Royal Statistical Society Series B: Statistical Methodology, 1985
- The Complexity of Enumeration and Reliability ProblemsSIAM Journal on Computing, 1979
- Existence of phase transitions in certain lattice gases with repulsive potentialLettere al Nuovo Cimento (1971-1985), 1972
- Prescribing a System of Random Variables by Conditional DistributionsTheory of Probability & Its Applications, 1970