Deterministically counting k-paths and trees parameterized by treewidth in single exponential time

Abstract

A valuable tool in evaluating the local structure of complex networks is the detection of network patterns, first described by Milo et al. (Science, 2002). Network patterns are small subgraphs that occur significantly more often in the network than in randomized networks. Since the occurrence of network motifs seems to be related to the function of the network, the counting of small subgraphs can be important when evaluating the quality of network models. In their 2015 paper, Bodlaender et al. (Information and Computation, 2015) introduced a determinant approach to connectivity problems that is used to deterministically count the number of Hamiltonian Cycles and Steiner Trees in c^tw |V|^O(1) time in host graphs G = (V, E) with a given tree decomposition of width tw, for some small constant c. This deter- minant approach is general enough to be applied to a range of counting problems, and a natural question is whether we can extend the approach in order to count network patterns. In this thesis, two deterministic algorithms based on the determinant ap- proach are presented. The first contribution is a dynamic program that counts k-paths in a host graph G = (V, E) with a given tree decompo- sition of width tw in O(18^tw k^2|V|) time. The second contribution is a generalization of the first algorithm, a dynamic program that counts the number of occurrences of some specific tree T inside host graph G, not accounting for internal symmetries of T . The presented algorithm takes ℓ^O(tw) (k/ℓ)^O(ℓ) |V| time for a tree T with k vertices and ℓ leaves. The cur- rent fastest algorithms utilizing the treewidth of the host graph for both these problems are elementary dynamic programs, and both presented algorithms provide significantly better running times by providing single- exponential time dependency on tw in the first case, and by removing the exponential dependency on k whenever ℓ is constant in the second case. Furthermore, the presented algorithms can be straightforwardly modified to solve fixed end-point #k-path, #k-cycle, #k-Tree and #k-Forest in single exponential time when parameterized by tw.