Rheinische Friedrich-Wilhelms-Universität Bonn Institut für Informatik
Abteilung V

Universität Bonn -> Institut für Informatik -> Abteilung V
CS-APX-Reports 2012 Copyright 2012 Universität Bonn, Institut für Informatik, Abt. V


Approximate Counting of Matchings in Sparse Uniform Hypergraphs
Marek Karpinski, Andrzej Rucinski and Edyta Szymanska
[Download PostScript] [Download PDF]

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.

Last Change: 11/05/14 at 11:00:03
Universität Bonn -> Institut für Informatik -> Abteilung V

Powered by Zope