Approximate counting of matchings in sparse uniform hypergraphs

DOI10.1137/1.9781611973037.9MaRDI QIDQ5194740zbMATH OpenOpenAlexFDO

Authors Andrzej Ruciński, Edyta Szymańska, Marek Karpinski

Publication date 17 September 2019

Published in 2013 Proceedings of the Tenth Workshop on Analytic Algorithmics and Combinatorics (ANALCO) (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1204.5335

Mathematics Subject Classification ID

Enumeration in graph theory (05C30) Hypergraphs (05C65) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Randomized algorithms (68W20) Approximation algorithms (68W25)

Abstract: In this paper we give a fully polynomial randomized approximation scheme (FPRAS) for the number of matchings in k-uniform hypergraphs whose intersection graphs contain few claws. Our method gives a generalization of the canonical path method of Jerrum and Sinclair to hypergraphs satisfying a local restriction. Our proof method depends on an application of the Euler tour technique for the canonical paths of the underlying Markov chains. On the other hand, we prove that it is NP-hard to approximate the number of matchings even for the class of k-uniform, 2-regular and linear hypergraphs, for all k >= 6, without the above restriction.

Recommendations

• Approximate counting of matchings in \((3,3)\)-hypergraphs
• Counting hypergraph matchings up to uniqueness threshold
• Counting hypergraph matchings up to uniqueness threshold
• On the random generation and counting of matchings in dense graphs
• On counting perfect matchings in general graphs

Cited in

(7)

• Counting hypergraph matchings up to uniqueness threshold
• Approximate counting of regular hypergraphs
• Computing the partition function for perfect matchings in a hypergraph
• Approximate counting of matchings in \((3,3)\)-hypergraphs
• A counting lemma for sparse pseudorandom hypergraphs
• Counting hypergraph matchings up to uniqueness threshold
• FPTAS for counting monotone CNF

This page was built for publication: Approximate counting of matchings in sparse uniform hypergraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5194740)