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(Delta1)). 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(Delta1)), the problem of approximating the value of the matching polynomial on graphs of maximum degree Delta with edge parameter gamma is #Phard.
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 #Phard 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:122:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771092},
ISSN = {18688969},
year = {2019},
volume = {132},
editor = {Christel Baier and Ioannis Chatzigiannakis and Paola Flocchini and Stefano Leonardi},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2019/10598},
URN = {urn:nbn:de:0030drops105983},
doi = {10.4230/LIPIcs.ICALP.2019.22},
annote = {Keywords: matchings, partition function, correlation decay, connective constant}
}
04.07.2019
Keywords: 

matchings, partition function, correlation decay, connective constant 
Seminar: 

46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)

Issue date: 

2019 
Date of publication: 

04.07.2019 