  Resolution parameters in graph clustering represent a size and quality
trade-off. We address the task of efficiently solving a parameterized graph
clustering objective for all values of a resolution parameter. Specifically, we
consider an objective we call LambdaPrime, involving a parameter $\lambda \in
(0,1)$. This objective is related to other parameterized clustering problems,
such as parametric generalizations of modularity, and captures a number of
specific clustering problems as special cases, including sparsest cut and
cluster deletion. While previous work provides approximation results for a
single resolution parameter, we seek a set of approximately optimal clusterings
for all values of $\lambda$ in polynomial time. In particular, we ask the
question, how small a family of clusterings suffices to optimize -- or to
approximately optimize -- the LambdaPrime objective over the full possible
spectrum of $\lambda$?
  We obtain a family of logarithmically many clusterings by solving the
parametric linear programming relaxation of LambdaPrime at a logarithmic number
of parameter values, and round their solutions using existing approximation
algorithms. We prove that this number is tight up to a constant factor.
Specifically, for a certain class of ring graphs, a logarithmic number of
feasible solutions is required to provide a constant-factor approximation for
the LambdaPrime LP relaxation in all parameter regimes. We additionally show
that for any graph with $n$ nodes and $m$ edges, there exists a set of $m$ or
fewer clusterings such that for every $\lambda \in (0,1)$, the family contains
an exact solution to the LambdaPrime objective. There also exists a set of
$O(\log n)$ clusterings that provide a $(1+\varepsilon)$-approximate solution
in all parameter regimes; we demonstrate simple graph classes for which these
bounds are tight.
