  Parameterized complexity theory offers a framework for a refined analysis of
hard algorithmic problems. Instead of expressing the running time of an
algorithm as a function of the input size only, running times are expressed
with respect to one or more parameters of the input instances. In this work we
follow the approach of parameterized complexity to provide a framework of
parameterized distributed complexity. The central notion of efficiency in
parameterized complexity is fixed-parameter tractability and we define the
distributed analogue Distributed-FPT (for Distributed in $\{Local, Congest,
Congested-Clique\}$) as the class of problems that can be solved in $f(k)$
communication rounds in the Distributed model of distributed computing, where
$k$ is the parameter of the problem instance and $f$ is an arbitrary computable
function. To classify hardness we introduce three hierarchies. The
Distributed-WEFT-hierarchy is defined analogously to the W-hierarchy in
parameterized complexity theory via reductions to the weighted circuit
satisfiability problem, but it turns out that this definition does not lead to
satisfying frameworks for the Local and Congest models. We then follow a
logical approach that leads to a more robust theory. We define the levels of
the Distributed-W-hierarchy and the Distributed-A-hierarchy that have
first-order model-checking problems as their complete problems via suitable
reductions.
