Article

Simple deterministic approximation algorithms for counting matchings

Authors:

David Gamarnik,

Prasad TetaliAuthors Info & Claims

STOC '07: Proceedings of the thirty-ninth annual ACM symposium on Theory of computing

Pages 122 - 127

https://doi.org/10.1145/1250790.1250809

Published: 11 June 2007 Publication History

Abstract

We construct a deterministic fully polynomial time approximationscheme (FPTAS) for computing the total number of matchings in abounded degree graph. Additionally, for an arbitrary graph, weconstruct a deterministic algorithm for computing approximately thenumber of matchings within running time exp(O(√n log²n)),where n is the number of vertices.

Our approach is based on the correlation decay technique originating in statistical physics. Previously thisapproach was successfully used for approximately counting thenumber of independent sets and colorings in some classes of graphs [1, 24, 6].Thus we add another problem to the small, but growing, class of P-complete problems for whichthere is now a deterministic FPTAS.

References

[1]

A. Bandyopadhyay and D. Gamarnik, Counting without sampling. New algorithms for enumeration problems using statistical physics., Proceedings of 17th ACM-SIAM Symposium on Discrete Algorithms (SODA), 2006.

Digital Library

[2]

N. Berger, C. Kenyon, E. Mossel, and Y. Peres, Glauber dynamics on trees and hyperbolic graphs, Proc. 42nd IEEE Symposium on Foundations of Computer Science (2001).

Digital Library

[3]

M. Bayati and C. Nair, A rigorous proof of cavity method for counting matchings, Annual Allerton Conference on Communication, Control and Computing, 2006.

[4]

R.L. Dobrushin, Prescribing a system of random variables by the help of conditional distributions, Theory of Probability and its Applications 15 (1970), 469--497.

[5]

M. Dyer, A. Sinclair, E. Vigoda, and D. Weitz, Mixing in time and space for lattice spin systems: a combinatorial view, Random Struct. & Alg. 24 (2004), 461--479.

Digital Library

[6]

D. Gamarnik and D. Katz, Correlation decay and deterministic FPTAS for counting list-colorings of a graph, Proceedings of 18th ACM-SIAM Symposium on Discrete Algorithms (SODA), 2007.

Digital Library

[7]

D. Gamarnik and D. Katz, A deterministic approximation algorithm for computing a permanent of a 0,1 matrix, Preprint on http://arxiv.org/abs/math.CO/0702039 (2007).

Digital Library

[8]

L.A. Goldberg, R. Martin, and M. Paterson, Strong spatial mixing with fewer colors for lattice graphs, SIAM J. Comput. 35 (2005), no. 2, 486--517.

Digital Library

[9]

C.D. Godsil, Matchings and walks in graphs, J. Graph Th. 5 (1981), 285--297.

[10]

O.J. Heilman and E.H. Lieb, Theory of monomer-dimer systems, Comm. Math. Phys. 25 (1972), 190--232.

[11]

M. Jerrum, Counting, sampling and integrating: algorithms and complexity, Lectures in Mathematics, ETH-Zurich, Birkhauser Verlag (2003).

[12]

M. Jerrum and A. Sinclair, The Markov chain Monte Carlo method: an approach to approximate counting and integration, Approximation algorithms for NP-hard problems (D. Hochbaum, ed.), PWS Publishing Company, Boston, MA, 1997.

Digital Library

[13]

K. Jung and D. Shah, Inference in Binary Pair-wise Markov Random Field through Self-Avoiding Walk, Preprint on http://arxiv.org/abs/cs.AI/0610111v2.

[14]

M. Jerrum, A. Sinclair, and E. Vigoda, A polynomial-time approximation algorithms for permanent of a matrix with non-negative entries, Journal of the Association for Computing Machinery 51 (2004), no. 4, 671--697.

Digital Library

[15]

M. Jerrum, L. Valiant, and V. Vazirani, Random generation of combinatorial structures from a uniform distribution, Theoret. Comput. Sci. 43 (1986), no2-3, 169--188.

Digital Library

[16]

JKahn and JH. Kim, Random matchings in regular graphs, Combinatorica 8 (1998), 201--226.

[17]

N. Linial, A. Samorodnitsky, and A. Wigderson, A deterministic strongly polynomial algorithm for matrix scaling and approximate permanents, Combinatorica 20 (2000), no4, 545--568.

[18]

A. Montanari and G. Semerjian, Rigorous inequalities between length and time scales in glassy systems, Preprint in arXiv.org (2006).

[19]

C. Nair and P. Tetali, The correlation decay (CD) tree and strong spatial mixing in multi-spin systems, Preprint on http://front.math.ucdavis.edu/math.PR/0701494.

[20]

A. Sinclair, Algorithms for random generation and counting: a Markov chain approach, Birkhauser Progress in Theoretical Computer Science Series, Birkhauser Verlag (1993).

Digital Library

[21]

S. Vadhan, The complexity of counting in sparse, regular, and planar graphs, SIAM Journal on Computing 31 (2001), no2, pp. 398--427.

Digital Library

[22]

L.G. Valiant, The complexity of computing the permanent, Theoretical Computer Science, 8 (1979), 189--201.

[23]

J. van den Berg, On the absence of phase transition in the monomer-dimer model, CWI reports, PNA-R9813, ISSN 1386-3711 (1998).

Digital Library

[24]

D. Weitz, Counting independent sets up to the tree threshold, Proc. 38th Ann. Symposium on the Theory of Computing (2006).

Digital Library

Cited By

Alimohammadi YDiaconis PRoghani MSaberi A(2023)Sequential importance sampling for estimating expectations over the space of perfect matchingsThe Annals of Applied Probability10.1214/22-AAP183433:2Online publication date: 1-Apr-2023
https://doi.org/10.1214/22-AAP1834
Feng WGuo HWang CWang JYin Y(2023)Towards derandomising Markov chain Monte Carlo2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS)10.1109/FOCS57990.2023.00120(1963-1990)Online publication date: 6-Nov-2023
https://doi.org/10.1109/FOCS57990.2023.00120
BRICEÑO R(2023)Counting independent sets in amenable groupsErgodic Theory and Dynamical Systems10.1017/etds.2023.38(1-55)Online publication date: 24-May-2023
https://doi.org/10.1017/etds.2023.38
Show More Cited By

Index Terms

Simple deterministic approximation algorithms for counting matchings
1. Computing methodologies
  1. Symbolic and algebraic manipulation
    1. Symbolic and algebraic algorithms
2. Theory of computation
  1. Design and analysis of algorithms
  2. Randomness, geometry and discrete structures

Recommendations

Distributed Local Approximation Algorithms for Maximum Matching in Graphs and Hypergraphs

We describe approximation algorithms in Linial's classic LOCAL model of distributed computing to find maximum-weight matchings in a hypergraph of rank $r$. Our main result is a deterministic algorithm to generate a matching which is an $O(r)$-approximation ...
Simple Deterministic Algorithms for Fully Dynamic Maximal Matching
Special Issue on SODA'12 and Regular Papers

A maximal matching can be maintained in fully dynamic (supporting both addition and deletion of edges) n-vertex graphs using a trivial deterministic algorithm with a worst-case update time of O(n). No deterministic algorithm that outperforms the naïve O(...
Almost Exact Matchings

In the exact matching problem we are given a graph G, some of whose edges are colored red, and a positive integer k. The goal is to determine if G has a perfect matching, exactly k edges of which are red. More generally if the matching number of G is m=...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

STOC '07: Proceedings of the thirty-ninth annual ACM symposium on Theory of computing

June 2007

734 pages

ISBN:9781595936318

DOI:10.1145/1250790

General Chair:
David Johnson
AT&T Labs - Research
,
Program Chair:
Uriel Feige
Microsoft Research and Weizmann Institute

Copyright © 2007 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 11 June 2007

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

STOC07

Sponsor:

STOC07: Symposium on Theory of Computing

June 11 - 13, 2007

California, San Diego, USA

Acceptance Rates

Overall Acceptance Rate 1,469 of 4,586 submissions, 32%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

65
Total Citations
View Citations
728
Total Downloads

Downloads (Last 12 months)21
Downloads (Last 6 weeks)2

Reflects downloads up to 26 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Alimohammadi YDiaconis PRoghani MSaberi A(2023)Sequential importance sampling for estimating expectations over the space of perfect matchingsThe Annals of Applied Probability10.1214/22-AAP183433:2Online publication date: 1-Apr-2023
https://doi.org/10.1214/22-AAP1834
Feng WGuo HWang CWang JYin Y(2023)Towards derandomising Markov chain Monte Carlo2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS)10.1109/FOCS57990.2023.00120(1963-1990)Online publication date: 6-Nov-2023
https://doi.org/10.1109/FOCS57990.2023.00120
BRICEÑO R(2023)Counting independent sets in amenable groupsErgodic Theory and Dynamical Systems10.1017/etds.2023.38(1-55)Online publication date: 24-May-2023
https://doi.org/10.1017/etds.2023.38
Regts G(2023)Absence of zeros implies strong spatial mixingProbability Theory and Related Fields10.1007/s00440-023-01190-z186:1-2(621-641)Online publication date: 3-Feb-2023
https://doi.org/10.1007/s00440-023-01190-z
Jain VPerkins WSah ASawhney MLeonardi SGupta A(2022)Approximate counting and sampling via local central limit theoremsProceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing10.1145/3519935.3519957(1473-1486)Online publication date: 9-Jun-2022
https://dl.acm.org/doi/10.1145/3519935.3519957
Anand KJerrum M(2022)Perfect Sampling in Infinite Spin Systems Via Strong Spatial MixingSIAM Journal on Computing10.1137/21M143743351:4(1280-1295)Online publication date: 1-Jan-2022
https://dl.acm.org/doi/10.1137/21M1437433
Liu JSinclair ASrivastava P(2022)Correlation Decay and Partition Function Zeros: Algorithms and Phase TransitionsSIAM Journal on Computing10.1137/20M1317384(FOCS19-200-FOCS19-252)Online publication date: 26-Jul-2022
https://doi.org/10.1137/20M1317384
Barvinok A(2022)Smoothed counting of 0–1 points in polyhedraRandom Structures & Algorithms10.1002/rsa.2113563:1(27-60)Online publication date: 30-Dec-2022
https://doi.org/10.1002/rsa.21135
Gamarnik D(2022)Correlation decay and the absence of zeros property of partition functionsRandom Structures & Algorithms10.1002/rsa.2108362:1(155-180)Online publication date: 18-Mar-2022
https://doi.org/10.1002/rsa.21083
Feng WGuo HYin Y(2022)Perfect sampling from spatial mixingRandom Structures & Algorithms10.1002/rsa.2107961:4(678-709)Online publication date: 18-Feb-2022
https://doi.org/10.1002/rsa.21079
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents