| dc.description.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. | |
