(Weighted) Counting of Matchings in Graph Families of Unbounded Treewidth

For a fixed graph family G, we are interested in the following computational problem, denoted PrMatch(G): - The input is an undirected graph G=(V, E) of G, together with (rational) probability values p(e) for each e \in E. - The output is the probability that G contains a simple path of length 2, when every edge e of G has a probability of existence p(e), independently from the others Equivalently, the output is one minus the probability to obtain a *matching* of G, i. e. , a subset of edges such that no two edges share an incident vertex. Note that we can set the edge probabilities to be 0, so we may assume that the family C is closed under subgraphs. It is known that if G has bounded treewidth, then PrMatch(G) can be solved in polynomial time. The result we want to present is that, essentially, bounding the treewidth is the only way to make this problem tractable. More precisely, we show that, for any graph family G that does not have bounded treewidth, and where high-treewidth graphs can be efficiently constructed, the problem PrMatch(G) is intractable (specifically, #P-hard under RP-reductions). During the presentation, we will present the proof for a simpler version of this result. We will show a reduction from the #P-hard problem of counting matchings in 3-regular planar graphs, which works by constructing polynomially many instances for the problem PrMatch(G) and obtaining a system of linear equations. We will show how, if the equations are invertible, we can recover the number of matchings of the original graph via multiple oracle calls to the problem. We will also discuss at a high level the intuitive idea and difficulties of the general proof, which uses the grid minor extraction theorem. This result extends an earlier result by Amarilli, Bourhis, and Senellart at PODS'16 where the same result is shown for a more complicated property in first-order logic; and it relates to the known intractability of computing tractable lineages over such graph families. This is ongoing work that is not yet published.

Authors

• Mikaël Monet

Keywords

No keywords are indexed for this paper.