Variance of the subgraph count for sparse Erd?s-Rényi graphs

We develop formulas for the variance of the number of copies of a small subgraph H in the Erd?s-Rényi random graph. The central technique employs a graph overlay polynomial encoding subgraph symmetries, which is of independent interest, that counts the number of copies overlapping H. In the sparse case, building on previous results of Janson, ?uczak, and Rucinski allows restriction of the polynomial to the asymptotically contributing portion either when H is connected with non-null 2-core, or when H is a tree. In either case we give a compact computational formula for the asymptotic variance in terms of a rooted tree overlay polynomial. Two cases for which the formula is valid in a range for which both the expected value and variance are finite are when H is a cycle with attached trees and when H is a tree.     

An exact algorithm for subgraph homeomorphism

The subgraph homeomorphism problem is to decide if there is an injective mapping of the vertices of a pattern graph into vertices of a host graph so that the edges of the pattern graph can be mapped into (internally) vertex-disjoint paths in the host graph. The restriction of subgraph homeomorphism where an injective mapping of the vertices of the pattern graph into vertices of the host graph is already given in the input instance is termed fixed-vertex subgraph homeomorphism.We show that fixed-vertex subgraph homeomorphism for a pattern graph on p vertices and a host graph on n vertices can be solved in time 2^n−pn^O(1) or in time 3^n−pn^O(1) and polynomial space. In effect, we obtain new non-trivial upper bounds on the time complexity of the problem of finding k vertex-disjoint paths and general subgraph homeomorphism.