Paper Info
Title
On Counting Perfect Matchings in General Graphs.
Abstract
Counting perfect matchings has played a central role in the theory of counting problems. The permanent, corresponding to bipartite graphs, was shown to be #P-complete to compute exactly by Valiant (1979), and a fully polynomial randomized approximation scheme (FPRAS) was presented by Jerrum, Sinclair, and Vigoda (2004) using a Markov chain Monte Carlo (MCMC) approach. However, it has remained an open question whether there exists an FPRAS for counting perfect matchings in general graphs. In fact, it was unresolved whether the same Markov chain defined by JSV is rapidly mixing in general. In this paper, we show that it is not. We prove torpid mixing for any weighting scheme on hole patterns in the JSV chain. As a first step toward overcoming this obstacle, we introduce a new algorithm for counting matchings based on the Gallai-Edmonds decomposition of a graph, and give an FPRAS for counting matchings in graphs that are sufficiently close to bipartite. In particular, we obtain a fixed-parameter tractable algorithm for counting matchings in general graphs, parameterized by the greatest "order" of a factor-critical subgraph.
Year
DOI
Venue
2018
10.1007/978-3-319-77404-6_63
Lecture Notes in Computer Science
DocType
Volume
ISSN
Conference
10807
0302-9743
Citations 
PageRank 
References 
0
0.34
3
Authors
3
Name
Order
Citations
PageRank
Daniel Stefankovic124328.65
Eric Vigoda274776.55
Wilmes, John390.86