Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH scholarly article en Curticapean, Radu http://www.dagstuhl.de/lipics License
when quoting this document, please refer to the following
DOI:
URN: urn:nbn:de:0030-drops-63847
URL:

Counting Matchings with k Unmatched Vertices in Planar Graphs

pdf-format:


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
Seminar: 24th Annual European Symposium on Algorithms (ESA 2016)
Issue date: 2016
Date of publication: 2016


DROPS-Home | Fulltext Search | Imprint Published by LZI