Jie Xue

Counting Paths and Trees via Exterior Algebra

We give randomized approximation algorithms for counting k-paths and k-forests in a host graph. Here k denotes the number of pattern vertices, n and m denote the numbers of host vertices and edges or arcs, {\epsilon} is the relative error, and {\delta} is the failure probability. Our main results are: 1. Paths: We appr...