Abstract
We present two new methods for counting all matchings in a graph. Both methods are alternatives to methods based on the Markov Chains and both are unbiased. The first one is a generalization of a Godman-Godsil estimator. We show that it works in time O(1.0878n∈-2) for general graphs. For dense graphs (every vertex is connected with at least ( 1/2 +α)n other vertices) it works in time O(n4+(6 ln 6)/α∈-2), where n is the number of vertices of a given graph and 0 < ∈ < 1 is an expected relative error. We also analyze the efficiency of the presented algorithm applied for random graphs. The second method uses importance sampling. This method works in exponential time but it can easily be enriched in some heuristics leading to very efficient algorithms in practice. Experiments show that our methods give better estimates than the Markow Chain approach
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Alexander Barvinok, Polynomial time algorithms to approximate permanents and mixed discriminants within a simply exponential factor, Random Structures and Algorithms 14 (1999), 29–61.
Alexander Barvinok, New Permanent Estimators Via Non-Commutative Determinants, preprint.
J. van den Berg and R. Brouwer, Random Sampling for the Monomer-Dimer Model on a Lattice, 1999 CWI Research Report.
Isabel Beichl and Francis Sullivan, Approximating the Permanent via Importance Sampling with Application to Dimer Covering Problem, Journal of computational Physics 149, 1, February 1999.
Steve Chien, Lars Rasmussen and Alistair Sinclair, Clifford Algebras and Approximating the Permanent, Proceedings of the 34th ACM Symposium on Theory of Computing, 2001, 712–721.
A. Frieze and M. Jerrum, An analysis of a Monte Carlo algorithm for estimating the permanent, Combinatorica, 15 (1995), 67–83.
C.D. Godsil and I. Gutman, On the matching polynomial of a graph, Algebraic Methods in Graph Theory, Vol. I, II, (Szeged, 1978), North-Holland, Amsterdam-New York, 1981, 241–249.
Ole J. Heilmann, Elliott H.Lieb, Theory of Monomer-Dimer Systems, Communications in mathematical Physics 25 (1972), 190–232.
Mark Jerrum and Alistair Sinclair, Approximating the permanent, SIAM Journal on Computing 18 (1989), 1149–1178.
Mark Jerrum and Alistair Sinclair, The Markow Chain Monte Carlo method: an approach to approximate counting and integration, in Approximation Algorithms for NP-hard Problems (Dorit Hochbaum, ed.),PWS 1996.
Mark Jerrum, Alistair Sinclair and Eric Vigoda, A polynomial-time approximation algorithm for the permanent of a matrix with non-negative entries, Electronic Colloquium on Computational Complexity, Report No. 79 (2000).
N. Karmarkar, R. Karp, R. Lipton, L. Lovász and M. Luby, A Monte Carlo algorithm for estimating the permanent, SIAM Journal on Computing22 (1993), 284–293.
Lars Eilstrup Rasmussen, Approximating the Permanent: a Simple Approach, Random Structures Algorithms 5 (1994), 349–361.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2003 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Sankowski, P. (2003). Alternative Algorithms for Counting All Matchings in Graphs. In: Alt, H., Habib, M. (eds) STACS 2003. STACS 2003. Lecture Notes in Computer Science, vol 2607. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-36494-3_38
Download citation
DOI: https://doi.org/10.1007/3-540-36494-3_38
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-00623-7
Online ISBN: 978-3-540-36494-8
eBook Packages: Springer Book Archive