Document Open Access Logo

Weighted Counting of Matchings in Unbounded-Treewidth Graph Families

Authors Antoine Amarilli , Mikaël Monet

PDF
Thumbnail PDF

File

LIPIcs.MFCS.2022.9.pdf
  • Filesize: 0.78 MB
  • 15 pages

Document Identifiers

Author Details

Antoine Amarilli
  • LTCI, Télécom Paris, Institut Polytechnique de Paris, France
Mikaël Monet
  • Univ. Lille, Inria, CNRS, Centrale Lille, UMR 9189 CRIStAL, F-59000 Lille, France

Funding

  • Amarilli, Antoine: Partially supported by the ANR project EQUUS ANR-19-CE48-0019 and by the Deutsche Forschungsgemeinschaft (DFG, German Research Foundation) – 431183758.

Acknowledgements

We thank Florent Capelli and Sébastien Tavenas for discussions on the problem, in particular on how to prove Proposition 5.2.

Cite AsGet BibTex

Antoine Amarilli and Mikaël Monet. Weighted Counting of Matchings in Unbounded-Treewidth Graph Families. In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 241, pp. 9:1-9:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.MFCS.2022.9

Abstract

We consider a weighted counting problem on matchings, denoted PrMatching(𝒢), on an arbitrary fixed graph family 𝒢. The input consists of a graph G ∈ 𝒢 and of rational probabilities of existence on every edge of G, assuming independence. The output is the probability of obtaining a matching of G in the resulting distribution, i.e., a set of edges that are pairwise disjoint. It is known that, if 𝒢 has bounded treewidth, then PrMatching(𝒢) can be solved in polynomial time. In this paper we show that, under some assumptions, bounded treewidth in fact characterizes the tractable graph families for this problem. More precisely, we show intractability for all graph families 𝒢 satisfying the following treewidth-constructibility requirement: given an integer k in unary, we can construct in polynomial time a graph G ∈ 𝒢 with treewidth at least k. Our hardness result is then the following: for any treewidth-constructible graph family 𝒢, the problem PrMatching(𝒢) is intractable. This generalizes known hardness results for weighted matching counting under some restrictions that do not bound treewidth, e.g., being planar, 3-regular, or bipartite; it also answers a question left open in [Amarilli et al., 2016]. We also obtain a similar lower bound for the weighted counting of edge covers.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Matchings and factors
Keywords
  • Treewidth
  • counting complexity
  • matchings
  • Fibonacci sequence

Metrics

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

Related Versions

Supplementary Materials

References

  1. Antoine Amarilli, Pierre Bourhis, and Pierre Senellart. Tractable lineages on treelike instances: Limits and extensions. In PODS, pages 355-370, 2016. URL: http://arxiv.org/abs/1604.02761.
  2. Antoine Amarilli, Mikaël Monet, and Pierre Senellart. Conjunctive queries on probabilistic graphs: Combined complexity. In PODS, pages 217-232, 2017. URL: http://arxiv.org/abs/1703.03201.
  3. Antoine Amarilli, Mikaël Monet, and Pierre Senellart. Connecting width and structure in knowledge compilation. In ICDT, volume 98, pages 6:1-6:17, 2018. URL: http://arxiv.org/abs/1709.06188.
  4. Antoine Amarilli and Mikaël Monet. Weighted counting of matchings in unbounded-treewidth graph families. In https://ac.tuwien.ac.at/mfcs2022/, 2022. Full version with proofs. URL: http://arxiv.org/abs/2205.00851.
  5. Stefan Arnborg, Jens Lagergren, and Detlef Seese. Easy problems for tree-decomposable graphs. Journal of Algorithms, 12(2):308-340, 1991. URL: https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.12.2544&rep=rep1&type=pdf.
  6. Paul Beame, Guy Van den Broeck, Eric Gribkoff, and Dan Suciu. Symmetric weighted first-order model counting. In PODS, pages 313-328, 2015. URL: http://arxiv.org/abs/1412.1505.
  7. Jin-Yi Cai and Xi Chen. Complexity Dichotomies for Counting Problems: Volume 1, Boolean Domain. Cambridge University Press, 2017. Google Scholar
  8. Jin-Yi Cai, Pinyan Lu, and Mingji Xia. Holographic reduction, interpolation and hardness. Computational Complexity, 21(4):573-604, 2012. URL: https://pages.cs.wisc.edu/~jyc/papers/interpolation08.pdf.
  9. Venkat Chandrasekaran, Nathan Srebro, and Prahladh Harsha. Complexity of Inference in Graphical Models. In UAI, pages 70-78, 2008. URL: https://dslpitt.org/uai/displayArticleDetails.jsp?mmnu=1&smnu=2&article_id=1343&proceeding_id=24.
  10. Chandra Chekuri and Julia Chuzhoy. Polynomial bounds for the grid-minor theorem. Journal of the ACM, 63(5):1-65, 2016. URL: http://arxiv.org/abs/1305.6577.
  11. Víctor Dalmau and Peter Jonsson. The complexity of counting homomorphisms seen from the other side. Theor. Comput. Sci., 329(1):315-323, 2004. URL: https://core.ac.uk/reader/81145200.
  12. Nilesh N. Dalvi and Dan Suciu. The dichotomy of probabilistic inference for unions of conjunctive queries. Journal of the ACM, 59(6):30, 2012. URL: https://homes.cs.washington.edu/~suciu/jacm-dichotomy.pdf.
  13. Robert Ganian, Petr Hliněnỳ, Alexander Langer, Jan Obdržálek, Peter Rossmanith, and Somnath Sikdar. Lower bounds on the complexity of MSO1 model-checking. JCSS, 1(80):180-194, 2014. URL: http://arxiv.org/abs/1109.5804.
  14. Catherine Greenhill. The complexity of counting colourings and independent sets in sparse graphs and hypergraphs. computational complexity, 9(1):52-72, 2000. URL: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.467.3100&rep=rep1&type=pdf.
  15. M.Monet (https://cstheory.stackexchange.com/users/38111/m monet). Holant problems and holographic reduction: simple graphs or multigraphs? Theoretical Computer Science Stack Exchange. URL: https://cstheory.stackexchange.com/q/43912 (version: 2019-05-18).
  16. Stephan Kreutzer and Siamak Tazari. Lower bounds for the complexity of monadic second-order logic. In LICS, pages 189-198, 2010. URL: http://arxiv.org/abs/1001.5019.
  17. Johan Kwisthout, Hans L. Bodlaender, and Linda C. van der Gaag. The necessity of bounded treewidth for efficient inference in Bayesian networks. In ECAI, pages 237-242, 2010. URL: http://www.booksonline.iospress.nl/Content/View.aspx?piid=17749.
  18. Salil P Vadhan. The complexity of counting in sparse, regular, and planar graphs. SIAM Journal on Computing, 31(2):398-427, 2001. URL: https://epubs.siam.org/doi/pdf/10.1137/S0097539797321602.
  19. Leslie G Valiant. The complexity of computing the permanent. Theoretical computer science, 8(2):189-201, 1979. URL: https://core.ac.uk/download/pdf/82500417.pdf.
  20. Leslie G. Valiant. The complexity of enumeration and reliability problems. SIAM J. Comput., 8(3):410-421, 1979. URL: https://www.math.cmu.edu/~af1p/Teaching/MCC17/Papers/enumerate.pdf.
  21. Wikipedia. Blossom algorithm, 2022. URL: https://en.wikipedia.org/wiki/Blossom_algorithm.
  22. Wikipedia. Cassini and Catalan identities, 2022. URL: https://en.wikipedia.org/wiki/Cassini_and_Catalan_identities.
  23. Wikipedia. Inverse function theorem, 2022. URL: https://en.wikipedia.org/wiki/Inverse_function_theorem.
  24. Wikipedia. Planar graphs, 2022. URL: https://en.wikipedia.org/wiki/Planar_graphs.
  25. Wikipedia. Treewidth, 2022. URL: https://en.wikipedia.org/wiki/Treewidth.
  26. Mingji Xia, Peng Zhang, and Wenbo Zhao. Computational complexity of counting problems on 3-regular planar graphs. Theor. Comput. Sci., 384(1):111-125, 2007. URL: https://core.ac.uk/download/pdf/82063901.pdf.
  27. Mingji Xia and Wenbo Zhao. #3-regular bipartite planar vertex cover is #P-complete. In International Conference on Theory and Applications of Models of Computation, pages 356-364. Springer, 2006. 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 Imprint Privacy Contact