  The study of algorithmic fairness received growing attention recently. This
stems from the awareness that bias in the input data for machine learning
systems may result in discriminatory outputs. For clustering tasks, one of the
most central notions of fairness is the formalization by Chierichetti, Kumar,
Lattanzi, and Vassilvitskii [NeurIPS 2017]. A clustering is said to be fair, if
each cluster has the same distribution of manifestations of a sensitive
attribute as the whole input set. This is motivated by various applications
where the objects to be clustered have sensitive attributes that should not be
over- or underrepresented.
  We discuss the applicability of this fairness notion to Correlation
Clustering. The existing literature on the resulting Fair Correlation
Clustering problem either presents approximation algorithms with poor
approximation guarantees or severely limits the possible distributions of the
sensitive attribute (often only two manifestations with a 1:1 ratio are
considered). Our goal is to understand if there is hope for better results in
between these two extremes. To this end, we consider restricted graph classes
which allow us to characterize the distributions of sensitive attributes for
which this form of fairness is tractable from a complexity point of view.
  While existing work on Fair Correlation Clustering gives approximation
algorithms, we focus on exact solutions and investigate whether there are
efficiently solvable instances. The unfair version of Correlation Clustering is
trivial on forests, but adding fairness creates a surprisingly rich picture of
complexities. We give an overview of the distributions and types of forests
where Fair Correlation Clustering turns from tractable to intractable. The most
surprising insight to us is the fact that the cause of the hardness of Fair
Correlation Clustering is not the strictness of the fairness condition.
