
We study the problem of exchange when 1) agents are endowed with
heterogeneous indivisible objects, and 2) there is no money. In general, no
rule satisfies the three central properties Paretoefficiency, individual
rationality, and strategyproofness \cite{Sonmez1999}. Recently, it was shown
that Top Trading Cycles is $\NP$hard to manipulate \cite{FujitaEA2015}, a
relaxation of strategyproofness. However, parameterized complexity is a more
appropriate framework for this and other economic settings. Certain aspects of
the problem  number of objects each agent brings to the table, goods up for
auction, candidates in an election \cite{consandlang2007}, legislative figures
to influence \cite{christian2007complexity}  may face natural bounds or are
fixed as the problem grows. We take a parameterized complexity approach to
indivisible goods exchange for the first time. Our results represent good and
bad news for TTC. When the size of the endowments $k$ is a fixed constant, we
show that the computational task of manipulating TTC can be performed in
polynomial time. On the other hand, we show that this parameterized problem is
$\W[1]$hard, and therefore unlikely to be \emph{fixed parameter tractable}.

We study the computational complexity of computing role colourings of graphs
in hereditary classes. We are interested in describing the family of hereditary
classes on which a role colouring with k colours can be computed in polynomial
time. In particular, we wish to describe the boundary between the "hard" and
"easy" classes. The notion of a boundary class has been introduced by Alekseev
in order to study such boundaries. Our main results are a boundary class for
the krole colouring problem and the related kcoupon colouring problem which
has recently received a lot of attention in the literature. The latter result
makes use of a technique for generating regular graphs of arbitrary girth which
may be of independent interest.

We give a new, simple distributed algorithm for graph colouring in paths and
cycles. Our algorithm is fast and selfcontained, it does not need any globally
consistent orientation, and it reduces the number of colours from $10^{100}$ to
$3$ in three iterations.

LCLs or locally checkable labelling problems (e.g. maximal independent set,
maximal matching, and vertex colouring) in the LOCAL model of computation are
very wellunderstood in cycles (toroidal 1dimensional grids): every problem
has a complexity of $O(1)$, $\Theta(\log^* n)$, or $\Theta(n)$, and the design
of optimal algorithms can be fully automated.
This work develops the complexity theory of LCL problems for toroidal
2dimensional grids. The complexity classes are the same as in the
1dimensional case: $O(1)$, $\Theta(\log^* n)$, and $\Theta(n)$. However, given
an LCL problem it is undecidable whether its complexity is $\Theta(\log^* n)$
or $\Theta(n)$ in 2dimensional grids.
Nevertheless, if we correctly guess that the complexity of a problem is
$\Theta(\log^* n)$, we can completely automate the design of optimal
algorithms. For any problem we can find an algorithm that is of a normal form
$A' \circ S_k$, where $A'$ is a finite function, $S_k$ is an algorithm for
finding a maximal independent set in $k$th power of the grid, and $k$ is a
constant.
Finally, partially with the help of automated design tools, we classify the
complexity of several concrete LCL problems related to colourings and
orientations.

We prove several results about the complexity of the role colouring problem.
A role colouring of a graph $G$ is an assignment of colours to the vertices of
$G$ such that two vertices of the same colour have identical sets of colours in
their neighbourhoods. We show that the problem of finding a role colouring with
$1< k <n$ colours is NPhard for planar graphs. We show that restricting the
problem to trees yields a polynomially solvable case, as long as $k$ is either
constant or has a constant difference with $n$, the number of vertices in the
tree. Finally, we prove that cographs are always $k$rolecolourable for
$1<k\leq n$ and construct such a colouring in polynomial time.