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.ESA.2016.33
URN: urn:nbn:de:0030-drops-63847
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2016/6384/
Go to the corresponding LIPIcs Volume Portal

Curticapean, Radu

Counting Matchings with k Unmatched Vertices in Planar Graphs

pdf-format:
LIPIcs-ESA-2016-33.pdf (0.6 MB)

Abstract

We consider the problem of counting matchings in planar graphs. While perfect matchings in planar graphs can be counted by a classical polynomial-time algorithm [Kasteleyn 1961], the problem of counting all matchings (possibly containing unmatched vertices, also known as defects) is known to be #P-complete 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 k-apex graphs (graphs that become planar after removing k vertices). Starting from a recent #W[1]-hardness proof for counting perfect matchings on k-apex 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 k-apex 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:1--33:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-015-6},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{57},
  editor =	{Piotr Sankowski and Christos Zaroliagis},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2016/6384},
  URN =		{urn:nbn:de:0030-drops-63847},
  doi =		{10.4230/LIPIcs.ESA.2016.33},
  annote =	{Keywords: counting complexity, parameterized complexity, matchings, planar graphs}
}

Keywords: counting complexity, parameterized complexity, matchings, planar graphs
Collection: 24th Annual European Symposium on Algorithms (ESA 2016)
Issue Date: 2016
Date of publication: 18.08.2016

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI