Curticapean, Radu
Counting Matchings with k Unmatched Vertices in Planar Graphs
Abstract
We consider the problem of counting matchings in planar graphs. While perfect matchings in planar graphs can be counted by a classical polynomialtime algorithm [Kasteleyn 1961], the problem of counting all matchings (possibly containing unmatched vertices, also known as defects) is known to be #Pcomplete on planar graphs [Jerrum 1987].
To interpolate between matchings and perfect matchings, we study the parameterized problem of counting matchings with k unmatched vertices in a planar graph G, on input G and k. This setting has a natural interpretation in statistical physics, and it is a special case of counting perfect matchings in kapex graphs (graphs that become planar after removing k vertices). Starting from a recent #W[1]hardness proof for counting perfect matchings on kapex graphs [Curtican and Xia 2015], we obtain:
 Counting matchings with k unmatched vertices in planar graphs is #W[1]hard.
 In contrast, given a plane graph G with s distinguished faces, there is an O(2^s n^3) time algorithm for counting those matchings with k unmatched vertices such that all unmatched vertices lie on the distinguished faces. This implies an f(k,s)n^O(1) time algorithm for counting perfect matchings in kapex graphs whose apex neighborhood is covered by s faces.
BibTeX  Entry
@InProceedings{curticapean:LIPIcs:2016:6384,
author = {Radu Curticapean},
title = {{Counting Matchings with k Unmatched Vertices in Planar Graphs}},
booktitle = {24th Annual European Symposium on Algorithms (ESA 2016)},
pages = {33:133:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770156},
ISSN = {18688969},
year = {2016},
volume = {57},
editor = {Piotr Sankowski and Christos Zaroliagis},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2016/6384},
URN = {urn:nbn:de:0030drops63847},
doi = {10.4230/LIPIcs.ESA.2016.33},
annote = {Keywords: counting complexity, parameterized complexity, matchings, planar graphs}
}
2016
Keywords: 

counting complexity, parameterized complexity, matchings, planar graphs 
Seminar: 

24th Annual European Symposium on Algorithms (ESA 2016)

Issue date: 

2016 
Date of publication: 

2016 