Abstract:
The problem of counting the number of subgraphs of a specific kind within an input graph G = (V,E)
has been extensively studied in literature. However, when it comes to designing good algorithms for
such problems, even the most simple cases, such as counting k - paths pose some challenges. One of
the many possible ways to cope with the hardness of such problems is by studying them from the lens
of Parameterized algorithms. In this thesis, we explore FPT approximation schemes (FPT-AS) for
counting k - paths in G.
In the first part, we look at additional parameterizations for the problem of k - path counting.
In particular, for directed graphs, we design a randomized FPT-AS, whose running time depends
upon the size of the hitting set for all k - paths in the graph, along with the parameter k. In case of
undirected graphs, we design a randomized FPT-AS, with running time dependent on k and the size
of the max-cut in G, conditioned on the existence of efficient sensitivity oracles of certain kind. For
both these algorithms, our primary tool is the KNAPSACK problem.
In the second part of the thesis, we look at the problem of counting the number of isomorphic copies
of a connected subgraph on k vertices within graphs of bounded degree. We do so by introducing
the notion of a subgraph-separating family, which is a natural extension to the Random-Separation
technique. Subsequently, by establishing its equivalence with parsimonious families in regular graphs,
we design a deterministic FPT-AS for #k-PATH.
iii
