Approximate Counting of Matchings in Sparse Uniform Hypergraphs

Details Approximate Counting of Matchings in Sparse Uniform Hypergraphs Approximate Counting of Matchings in Sparse Uniform Hypergraphs

2012-04-24

arxiv.org/abs/1204.5335v1

Computer Science

Data Structures and Algorithms

arXiv admin note: substantial text overlap with arXiv:1202.5885

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Approximate Counting of Matchings in Sparse Uniform Hypergraphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Approximate Counting of Matchings in Sparse Uniform Hypergraphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Approximate Counting of Matchings in Sparse Uniform Hypergraphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-519810