  In this work, we initiate a thorough study of parameterized graph
optimization problems in the distributed setting. In a parameterized problem,
an algorithm decides whether a solution of size bounded by a \emph{parameter}
$k$ exists and if so, it finds one. We study fundamental problems, including
Minimum Vertex Cover (MVC), Maximum Independent Set (MaxIS), Maximum Matching
(MaxM), and many others, in both the LOCAL and CONGEST distributed computation
models. We present lower bounds for the round complexity of solving
parameterized problems in both models, together with optimal and near-optimal
upper bounds.
  Our results extend beyond the scope of parameterized problems. We show that
any LOCAL $(1+\epsilon)$-approximation algorithm for the above problems must
take $\Omega(\epsilon^{-1})$ rounds. Joined with the algorithm of [GKM17] and
the $\Omega(\sqrt{\frac{\log n}{\log\log n}})$ lower bound of [KMW16], this
settles the complexity of $(1+\epsilon)$-approximating MVC, MaxM and MaxIS at
$(\epsilon^{-1}\log n)^{\Theta(1)}$. We also show that our parameterized
approach reduces the runtime of exact and approximate CONGEST algorithms for
MVC and MaxM if the optimal solution is small, without knowing its size
beforehand. Finally, we propose the first deterministic $o(n^2)$ rounds CONGEST
algorithms that approximate MVC and MaxM within a factor strictly smaller than
$2$.
