TY - GEN
T1 - Weighted Counting of Matchings in Unbounded-Treewidth Graph Families
AU - Amarilli, Antoine
AU - Monet, Mikaël
N1 - Publisher Copyright:
© 2022 Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. All rights reserved.
PY - 2022/8/1
Y1 - 2022/8/1
N2 - 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.
AB - 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.
KW - Fibonacci sequence
KW - Treewidth
KW - counting complexity
KW - matchings
U2 - 10.4230/LIPIcs.MFCS.2022.9
DO - 10.4230/LIPIcs.MFCS.2022.9
M3 - Conference contribution
AN - SCOPUS:85137598366
T3 - Leibniz International Proceedings in Informatics, LIPIcs
BT - 47th International Symposium on Mathematical Foundations of Computer Science, MFCS 2022
A2 - Szeider, Stefan
A2 - Ganian, Robert
A2 - Silva, Alexandra
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
T2 - 47th International Symposium on Mathematical Foundations of Computer Science, MFCS 2022
Y2 - 22 August 2022 through 26 August 2022
ER -