2026-08-16T18:58:36Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:6384 2024-03-06T10:38:07Z ddc:004 open_access

Counting Matchings with k Unmatched Vertices in Planar Graphs Curticapean, Radu counting complexity parameterized complexity matchings planar graphs 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Radu Curticapean 2016 Is Part Of LIPIcs, Volume 57, 24th Annual European Symposium on Algorithms (ESA 2016) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2016.33 urn:nbn:de:0030-drops-63847 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2016.33 eng https://creativecommons.org/licenses/by/3.0/legalcode