Passer à la navigation principale Passer à la recherche Passer au contenu principal

Weighted Counting of Matchings in Unbounded-Treewidth Graph Families

  • Université de Lille

Résultats de recherche: Le chapitre dans un livre, un rapport, une anthologie ou une collection › Contribution à une conférence › Revue par des pairs

1 Citation (Scopus)

Résumé

We consider a weighted counting problem on matchings, denoted PrMatchingpGq, on an arbitrary fixed graph family G. The input consists of a graph G P 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 G has bounded treewidth, then PrMatchingpGq 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 G satisfying the following treewidth-constructibility requirement: Given an integer k in unary, we can construct in polynomial time a graph G P G with treewidth at least k. Our hardness result is then the following: For any treewidth-constructible graph family G, the problem PrMatchingpGq 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 [1]. We also obtain a similar lower bound for the weighted counting of edge covers.

langue originaleAnglais
titre47th International Symposium on Mathematical Foundations of Computer Science, MFCS 2022
rédacteurs en chefStefan Szeider, Robert Ganian, Alexandra Silva
EditeurSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Electronique)9783959772563
Les DOIs
étatPublié - 1 août 2022
Evénement47th International Symposium on Mathematical Foundations of Computer Science, MFCS 2022 - Vienna, Autriche
Durée: 22 août 2022 → 26 août 2022

Série de publications

NomLeibniz International Proceedings in Informatics, LIPIcs
Volume241
ISSN (imprimé)1868-8969

Une conférence

Une conférence47th International Symposium on Mathematical Foundations of Computer Science, MFCS 2022
Pays/TerritoireAutriche
La villeVienna
période22/08/22 → 26/08/22

Empreinte digitale

Examiner les sujets de recherche de « Weighted Counting of Matchings in Unbounded-Treewidth Graph Families ». Ensemble, ils forment une empreinte digitale unique.

Contient cette citation