Counting Small Subgraphs with a Specified Property in a Large Graph

Tuesday, March 17, 2015 - 9:30am - 10:10am
Klaus 2443
Mark Jerrum (Queen Mary and Westfield College)
Given a graph G, we are interested in counting induced k-vertex subgraphs satisfying a certain specified property Phi. Many counting problems fit into this general framework. If we fix k, we can certainly count subgraphs satisfying Phi in time O(n^k) by brute force. The question prompted by parameterised complexity is: is there universal constant c, and an algorithm A for counting these subgraphs, such that for all k the running time of A is O(n^c). If k is small, and n large, such an algorithm might be acceptable, even if the dependence on k implicit in the O-notation is rather strong.

There has been substantial progress on this topic recently, and I'll spend a little time reviewing this. Then, I'll describe a couple of general results, one of them concerning the existence of efficient randomised algorithms for approximately counting subgraphs in the parameterised setting. The special case where Phi is the property of being connected will be a running example. This is joint work with Kitty Meeks (Glasgow).