An FPRAS for Counting Path and Tree Labelings
November 20, 2019 (GHC 6115)

In this talk, we will discuss two recent results which demonstrate the existence of fully-polynomial time randomized approximation schemes (FPRAS) and polynomial time uniform samplers for structured sets of path and tree labelings.

1) Given a directed graph G=(V,E) with edge labels L(e) \in {1,2,...,k}, we consider the problem of counting the number of path labelings of length n in G. Here, the label of a path P = (e_1,e_2,...,e_n) is L(P) = (L(e_1),L(e_2),..., L(e_n)) \in [k]^n. This problem is equivalent to the well-studied problem of counting the number of words of length n in a regular language. While polynomial time exact algorithms exist for special cases, in general the problem is #P-Hard. However, this fact does not rule out the possibility of efficient approximation algorithms. Prior to this work, the best known approximation algorithm was a quasi-polynomial time scheme due to Kannan, Sweedyk, and Mahaney 95'. In this work, we improve this result by giving the first FPRAS and polynomial-time uniform sampler.

2) A generalization of the above is to allow the paths to "branch", in the sense that from a vertex one can take edges to *multiple* other vertices, each of which in turn can move to multiple other vertices, resulting in a tree. This family of labelled trees are known as the regular tree languages, and can model a substantially richer class of objects such as constraint satisfaction problems (CSP's) with bounded hypertree width, monadic second order logic (MSO), DNNF circuits, and nested calls in programs (to name just a few). We introduce the first FPRAS and uniform sampler for the set of trees of size n in a regular tree language, which improves on the prior state of the art QPRAS due to Gore and Jerrum 97'.

This is a joint work with Marcelo Arenas, Luis Alberto Croquevielle, and Cristian Riveros from PUC Chile.