  The maximum modularity of a graph is a parameter widely used to describe the
level of clustering or community structure in a network. Determining the
maximum modularity of a graph is known to be NP-complete in general, and in
practice a range of heuristics are used to construct partitions of the
vertex-set which give lower bounds on the maximum modularity but without any
guarantee on how close these bounds are to the true maximum. In this paper we
investigate the parameterised complexity of determining the maximum modularity
with respect to various standard structural parameterisations of the input
graph G. We show that the problem belongs to FPT when parameterised by the size
of a minimum vertex cover for G, and is solvable in polynomial time whenever
the treewidth or max leaf number of G is bounded by some fixed constant; we
also obtain an FPT algorithm, parameterised by treewidth, to compute any
constant-factor approximation to the maximum modularity. On the other hand we
show that the problem is W[1]-hard (and hence unlikely to admit an FPT
algorithm) when parameterised simultaneously by pathwidth and the size of a
minimum feedback vertex set.
