Spring 2016

Counting with Bounded Treewidth

Friday, April 1st, 2016 11:45 am12:30 pm

Add to Calendar

We consider counting CSPs and Holant problems defined by general asymmetric constraints of unbounded arity. We give a fixed parameter tractable (FPT) algorithm for Holant problems, in terms of two parameters: the treewidth of the underlying graph and the "regularity" of the signatures. We define a notion of regularity for the signatures (constraint functions). And we show that the Holant problem defined by r-regular signatures on a graph of treewidth k can be computed within time r^O(k) poly(n). This covers the known FPT algorithms in terms of treewidth for spin systems, counting graph homomorphisms, counting CSPs with bounded-arity constraints, Holant problems and tensor networks on bounded-degree graphs, and counting matchings and perfect matchings on general graphs.

PDF icon Counting with Bounded Treewidth5.19 MB