Approximate counting of matchings in sparse uniform hypergraphs
Authors:
- Marek Karpiński,
- Andrzej Ruciński,
- Edyta Barbara Szymańska
Abstract
In this paper we give a fully polynomial randomized approximation scheme (FPRAS) for the number of matchings in κ 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. The proof 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 2-regular, linear, κ-uniform hypergraphs, for all κ ≥ 6, without the above restriction.
- Record ID
- UAM9c359251cd4d40949fe5c81fb8e7865d
- Author
- Pages
- 71-78
- Book
- Nebel Marcus, Marcus Nebel Szpankowski Wojciech Wojciech Szpankowski (eds.): 2013 Proceedings of the Meeting on Analytic Algorithmics and Combinatorics 2013. New Orleans, Louisiana, USA 6 January 2013 (ANALCO), 2013, Philadelphia, Society for Industrial and Applied Mathematics, 106 p., ISBN 978-1-61197-254-2. DOI:10.1137/1.9781611973037 Opening in a new tab
- DOI
- DOI:10.1137/1.9781611973037.9 Opening in a new tab
- URL
- https://epubs.siam.org/doi/10.1137/1.9781611973037.9 Opening in a new tab
- Language
- (en) English
- File
-
- File: 1
- 1.9781611973037.9.pdf
-
- Score (nominal)
- 0
- Score
- Publication indicators
- = 3
Share
- Uniform Resource Identifier
- https://researchportal.amu.edu.pl/info/article/UAM9c359251cd4d40949fe5c81fb8e7865d/
- URN
urn:amu-prod:UAM9c359251cd4d40949fe5c81fb8e7865d
* presented citation count is obtained through Internet information analysis and it is close to the number calculated by the Publish or PerishOpening in a new tab system.