Document Open Access Logo

Counting Matchings with k Unmatched Vertices in Planar Graphs

Author Radu Curticapean

PDF
Thumbnail PDF

File

LIPIcs.ESA.2016.33.pdf
  • Filesize: 0.59 MB
  • 17 pages

Document Identifiers

Author Details

Radu Curticapean

Cite As Get BibTex

Radu Curticapean. Counting Matchings with k Unmatched Vertices in Planar Graphs. In 24th Annual European Symposium on Algorithms (ESA 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 57, pp. 33:1-33:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.ESA.2016.33

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.

Subject Classification

Keywords
  • counting complexity
  • parameterized complexity
  • matchings
  • planar graphs

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Manindra Agrawal. Determinant versus permanent. In Proceedings of the 25th International Congress of Mathematicians, ICM 2006, volume 3, pages 985-997, 2006. Google Scholar
  2. Markus Bläser and Radu Curticapean. Weighted counting of k-matchings is #W[1]-hard. In IPEC, pages 171-181, 2012. URL: http://dx.doi.org/10.1007/978-3-642-33293-7_17.
  3. P. Bürgisser. Completeness and Reduction in Algebraic Complexity Theory. Number 7 in Algorithms and Computation in Mathematics. Springer Verlag, 2000. 168 + xii pp. Google Scholar
  4. Jin-Yi Cai, Pinyan Lu, and Mingji Xia. A computational proof of complexity of some restricted counting problems. In TAMC 2009, pages 138-149, 2009. Google Scholar
  5. Jianer Chen, Benny Chor, Mike Fellows, Xiuzhen Huang, David W. Juedes, Iyad A. Kanj, and Ge Xia. Tight lower bounds for certain parameterized NP-hard problems. Inf. Comput., 201(2):216-231, 2005. Google Scholar
  6. Radu Curticapean. Counting matchings of size k is #W[1]-hard. In ICALP 2013, pages 352-363, 2013. URL: http://dx.doi.org/10.1007/978-3-642-39206-1_30.
  7. Radu Curticapean. Counting perfect matchings in graphs that exclude a single-crossing minor. CoRR, abs/1406.4056, 2014. Google Scholar
  8. Radu Curticapean. Block interpolation: A framework for tight exponential-time counting complexity. In ICALP 2015, pages 380-392, 2015. Google Scholar
  9. Radu Curticapean. Parity separation: A scientifically proven method for permanent weight loss. CoRR, abs/1511.07480, 2015. Google Scholar
  10. Radu Curticapean. The simple, little and slow things count: on parameterized counting complexity. PhD thesis, Saarland University, 2015. Google Scholar
  11. Radu Curticapean and Dániel Marx. Complexity of counting subgraphs: Only the boundedness of the vertex-cover number counts. In FOCS 2014, pages 130-139, 2014. Google Scholar
  12. Radu Curticapean and Mingji Xia. Parameterizing the permanent: Genus, apices, minors, evaluation mod 2^k. In FOCS 2015, pages 994-1009, 2015. Google Scholar
  13. Holger Dell, Thore Husfeldt, Dániel Marx, Nina Taslaman, and Martin Wahlen. Exponential time complexity of the permanent and the Tutte polynomial. ACM Transactions on Algorithms, 10(4):21, 2014. Google Scholar
  14. Erik D. Demaine, MohammadTaghi Hajiaghayi, and Ken-ichi Kawarabayashi. Approximation algorithms via structural results for apex-minor-free graphs. In ICALP 2009, pages 316-327, 2009. Google Scholar
  15. Jörg Flum and Martin Grohe. The parameterized complexity of counting problems. SIAM Journal on Computing, 33(4):892-922, 2004. Google Scholar
  16. Jörg Flum and Martin Grohe. Parameterized Complexity Theory. Springer, 2006. Google Scholar
  17. Markus Frick. Generalized model-checking over locally tree-decomposable classes. Theory Comput. Syst., 37(1):157-191, 2004. Google Scholar
  18. Anna Galluccio and Martin Loebl. On the theory of Pfaffian orientations. I. Perfect matchings and permanents. Electronic Journal of Combinatorics, 6, 1998. Google Scholar
  19. Frank Harary. Graph theory. Addison-Wesley, 1991. Google Scholar
  20. Haruo Hosoya. Topological index. A newly proposed quantity characterizing the topological nature of structural isomers of saturated hydrocarbons. Bulletin of the Chemical Society of Japan, 44(9):2332-2339, 1971. Google Scholar
  21. Russell Impagliazzo and Ramamohan Paturi. On the complexity of k-SAT. Journal of Computer and System Sciences, 62(2):367-375, 2001. Google Scholar
  22. Russell Impagliazzo, Ramamohan Paturi, and Francis Zane. Which problems have strongly exponential complexity? J. Comput. System Sci., 63(4):512-530, 2001. Google Scholar
  23. Mark Jerrum. Two-dimensional monomer-dimer systems are computationally intractable. Journal of Statistical Physics, 48(1-2):121-134, 1987. Google Scholar
  24. Mark Jerrum and Alistair Sinclair. Approximating the permanent. SIAM J. Comput., 18(6):1149-1178, 1989. Google Scholar
  25. Mark Jerrum, Alistair Sinclair, and Eric Vigoda. A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries. J. ACM, 51(4):671-697, 2004. Google Scholar
  26. Pieter W. Kasteleyn. The statistics of dimers on a lattice: I. The number of dimer arrangements on a quadratic lattice. Physica, 27(12):1209-1225, 1961. Google Scholar
  27. Pieter W. Kasteleyn. Graph Theory and Crystal Physics. In Graph Theory and Theoretical Physics, pages 43-110. Academic Press, 1967. Google Scholar
  28. Charles Little. An extension of Kasteleyn’s method of enumerating the 1-factors of planar graphs. In Combinatorial Mathematics, LNCS, pages 63-72. Springer, 1974. Google Scholar
  29. Daniel Lokshtanov, Dániel Marx, and Saket Saurabh. Lower bounds based on the Exponential Time Hypothesis. Bulletin of the EATCS, 84:41-71, 2011. Google Scholar
  30. Tullio Regge and Riccardo Zecchina. Combinatorial and topological approach to the 3d ising model. Journal of Physics A: Mathematical and General, 33(4):741, 2000. Google Scholar
  31. Neil Robertson and Paul D. Seymour. Graph minors. XVI. Excluding a non-planar graph. J. Comb. Theory, Ser. B, 89(1):43-76, 2003. Google Scholar
  32. Simon Straub, Thomas Thierauf, and Fabian Wagner. Counting the number of perfect matchings in K₅-free graphs. In CCC 2014, pages 66-77, 2014. Google Scholar
  33. H. N. V. Temperley and Michael E. Fisher. Dimer problem in statistical mechanics - an exact result. Philosophical Magazine, 6(68):1478-6435, 1961. Google Scholar
  34. Leslie G. Valiant. The complexity of computing the permanent. Theoret. Comput. Sci., 8(2):189-201, 1979. Google Scholar
  35. Leslie G. Valiant. The complexity of enumeration and reliability problems. SIAM J. Comput., 8(3):410-421, 1979. Google Scholar
  36. Leslie G. Valiant. Holographic algorithms. SIAM J. Comput., 37(5):1565-1594, 2008. URL: http://dx.doi.org/10.1137/070682575.
  37. Johan M. M. van Rooij, Hans L. Bodlaender, and Peter Rossmanith. Dynamic programming on tree decompositions using generalised fast subset convolution. In ESA 2009, pages 566-577, 2009. Google Scholar
  38. Vijay V. Vazirani. NC algorithms for computing the number of perfect matchings in K_3,3-free graphs and related problems. Inf. Comput., 80(2):152-164, 1989. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact