License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICALP.2019.22
URN: urn:nbn:de:0030-drops-105983
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2019/10598/
Bezáková, Ivona ;
Galanis, Andreas ;
Goldberg, Leslie Ann ;
Stefankovic, Daniel
The Complexity of Approximating the Matching Polynomial in the Complex Plane
Abstract
We study the problem of approximating the value of the matching polynomial on graphs with edge parameter gamma, where gamma takes arbitrary values in the complex plane.
When gamma is a positive real, Jerrum and Sinclair showed that the problem admits an FPRAS on general graphs. For general complex values of gamma, Patel and Regts, building on methods developed by Barvinok, showed that the problem admits an FPTAS on graphs of maximum degree Delta as long as gamma is not a negative real number less than or equal to -1/(4(Delta-1)). Our first main result completes the picture for the approximability of the matching polynomial on bounded degree graphs. We show that for all Delta >= 3 and all real gamma less than -1/(4(Delta-1)), the problem of approximating the value of the matching polynomial on graphs of maximum degree Delta with edge parameter gamma is #P-hard.
We then explore whether the maximum degree parameter can be replaced by the connective constant. Sinclair et al. showed that for positive real gamma it is possible to approximate the value of the matching polynomial using a correlation decay algorithm on graphs with bounded connective constant (and potentially unbounded maximum degree). We first show that this result does not extend in general in the complex plane; in particular, the problem is #P-hard on graphs with bounded connective constant for a dense set of gamma values on the negative real axis. Nevertheless, we show that the result does extend for any complex value gamma that does not lie on the negative real axis. Our analysis accounts for complex values of gamma using geodesic distances in the complex plane in the metric defined by an appropriate density function.
BibTeX - Entry
@InProceedings{bezkov_et_al:LIPIcs:2019:10598,
author = {Ivona Bez{\'a}kov{\'a} and Andreas Galanis and Leslie Ann Goldberg and Daniel Stefankovic},
title = {{The Complexity of Approximating the Matching Polynomial in the Complex Plane}},
booktitle = {46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)},
pages = {22:1--22:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-109-2},
ISSN = {1868-8969},
year = {2019},
volume = {132},
editor = {Christel Baier and Ioannis Chatzigiannakis and Paola Flocchini and Stefano Leonardi},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2019/10598},
URN = {urn:nbn:de:0030-drops-105983},
doi = {10.4230/LIPIcs.ICALP.2019.22},
annote = {Keywords: matchings, partition function, correlation decay, connective constant}
}
|
Keywords: |
|
matchings, partition function, correlation decay, connective constant |
|
Collection: |
|
46th International Colloquium on Automata, Languages, and Programming (ICALP 2019) |
|
Issue Date: |
|
2019 |
|
Date of publication: |
|
04.07.2019 |
