Humboldt University of Berlin,
Germanykatrin.casel@hpi.dehttps://orcid.org/0000-0001-6146-8684 Hasso Plattner
Institute, University of Potsdam,
Germanytobias.friedrich@hpi.dehttps://orcid.org/0000-0003-0076-6308 Faculty of
Computer Science, University of Vienna,
Austriamartin.schirneck@univie.ac.athttps://orcid.org/0000-0001-7086-5577
Hasso Plattner Institute, University of Potsdam,
Germanysimon.wietheger@student.hpi.dehttps://orcid.org/0000-0002-0734-0708
Katrin Casel, Tobias Friedrich, Martin Schirneck, and Simon Wietheger
<ccs2012> <concept> <concept_id>10003752.10003809.10003635</concept_id>
<concept_desc>Theory of computation Graph algorithms analysis</concept_desc>
<concept_significance>500</concept_significance> </concept> <concept>
<concept_id>10003456.10003462</concept_id> <concept_desc>Social and
professional topics Computing / technology policy</concept_desc>
<concept_significance>300</concept_significance> </concept> <concept>
<concept_id>10003752.10003809.10011254.10011258</concept_id>
<concept_desc>Theory of computation Dynamic programming</concept_desc>
<concept_significance>300</concept_significance> </concept> </ccs2012>
[500]Theory of computation Graph algorithms analysis [300]Social and
professional topics Computing / technology policy [300]Theory of computation
Dynamic programming

###### Acknowledgements.

Kunal Talwar 1 4th Symposium on Foundations of Responsible Computing (FORC
2023) FORC 2023 FORC 2023 June 7–9, 2023 Stanford, CA, United States

# Fair Correlation Clustering in Forests

Katrin Casel  Tobias Friedrich  Martin Schirneck  Simon Wietheger

###### Abstract

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. Most research on this version of fair clustering
has focused on centriod-based objectives.

In contrast, 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.

As the most surprising insight, we consider the fact that the cause of the
hardness of Fair Correlation Clustering is not the strictness of the fairness
condition. We lift most of our results to also hold for the relaxed version of
the fairness condition. Instead, the source of hardness seems to be the
distribution of the sensitive attribute. On the positive side, we identify
some reasonable distributions that are indeed tractable. While this
tractability is only shown for forests, it may open an avenue to design
reasonable approximations for larger graph classes.

###### keywords:

correlation clustering, disparate impact, fair clustering, relaxed fairness

###### category:

##  1 Introduction

In the last decade, the notion of fairness in machine learning has
increasingly attracted interest, see for example the review by Pessach and
Schmueli [32]. Feldman, Friedler, Moeller, Scheidegger, and Venkatasubramanian
[26] formalize fairness based on a US Supreme Court decision on disparate
impact from 1971. It requires that sensitive attributes like gender or skin
color should neither be explicitly considered in decision processes like
hiring but also should the manifestations of sensitive attributes be
proportionally distributed in all outcomes of the decision process. Feldman et
al. formalize this notion for classification tasks. Chierichetti, Kumar,
Lattanzi, and Vassilvitskii [19] adapt this concept for clustering tasks.

In this paper we employ the same disparate impact based understanding of
fairness. Formally, the objects to be clustered have a color assigned to them
that represents some sensitive attribute. Then, a clustering of these colored
objects is called _fair_ if for each cluster and each color the ratio of
objects of that color in the cluster corresponds to the total ratio of
vertices of that color. More precisely, a clustering is _fair_ , if it
partitions the set of objects into _fair subsets_.

######  Definition 1.1 (Fair Subset).

Let $U$ be a finite set of objects colored by a function $c\colon
U\rightarrow[k]$ for some $k\in\mathbb{N}_{>0}$. Let $U_{i}=\\{u\in U\mid
c(u)=i\\}$ be the set of objects of color $i$ for all $i\in[k]$. Then, a set
$S\subseteq U$ is fair if and only if for all colors $i\in[k]$ we have
$\frac{|S\cap U_{i}|}{|S|}=\frac{|U_{i}|}{|U|}$.

To understand how this notion of fairness affects clustering decisions,
consider the following example. Imagine that an airport security wants to find
clusters among the travelers to assign to each group a level of potential risk
with corresponding anticipating measures. There are attributes like skin color
that should not influence the assignment to a risk level. A bias in the data,
however, may lead to some colors being over- or underrepresented in some
clusters. Simply removing the skin color attribute from the data may not
suffice as it may correlate with other attributes. Such problems are
especially likely if one of the skin colors is far less represented in the
data than others. A fair clustering finds the optimum clustering such that for
each risk level the distribution of skin colors is fair, by requiring the
distribution of each cluster to roughly match the distribution of skin colors
among all travelers.

The seminal fair clustering paper by Chierichetti et al. [19] introduced this
notion of fairness for clustering and studied it for the objectives $k$-center
and $k$-median. Their work was extended by Bera, Chakrabarty, Flores, and
Negahbani [11], who relax the fairness constraint in the sense of requiring
upper and lower bounds on the representation of a color in each cluster. More
precisely, they define the following generalization of fair sets.

######  Definition 1.2 (Relaxed Fair Set).

For a finite set $U$ and coloring $c\colon U\rightarrow[k]$ for some
$k\in\mathbb{N}_{>0}$ let $p_{i},q_{i}\in\mathbb{Q}$ with
$0<p_{i}\leqslant\frac{|U_{i}|}{|U|}\leqslant q_{i}<1$ for all $i\in[k]$,
where $U_{i}=\\{u\in U\mid c(u)=i\\}$. A set $S\subseteq U$ is relaxed fair
with respect to $q_{i}$ and $p_{i}$ if and only if $p_{i}\leqslant\frac{|S\cap
U_{i}|}{|S|}\leqslant q_{i}$ for all $i\in[k]$.

Following these results, this notion of (relaxed) fairness was extensively
studied for centroid-based clustering objectives with many positive results.

For example, Bercea et al. [12] give bicreteira constant-factor approximations
for facility location type problems like $k$-center and $k$-median.
Bandyapadhyay, Fomin and Simonov [7] use the technique of fair coresets
introduced by Schmidt, Schwiegelshohn, and Sohler [34] to give constant factor
approximations for many centroid-based clustering objectives; among many other
results, they give a PTAS for fair $k$-means and $k$-median in Euclidean
space. Fairness for centroid-based objectives seems to be so well understood,
that most research already considers more generalized settings, like streaming
[34], or imperfect knowledge of group membership [25].

In comparison, there are few (positive) results for this fairness notion
applied to graph clustering objectives. The most studied with respect to
fairness among those is Correlation Clustering, arguably the most studied
graph clustering objective. For Correlation Clustering we are given a pairwise
similarity measure for a set of objects and the aim is to find a clustering
that minimizes the number of similar objects placed in separate clusters and
the number of dissimilar objects placed in the same cluster. Formally, the
input to Correlation Clustering is a graph $G=(V,E)$, and the goal is to find
a partition $\mathcal{P}$ of $V$ that minimizes the Correlation Clustering
cost defined as

$\displaystyle\text{cost}(G,\mathcal{P})=|\hskip
1.00006pt\\{\\{u,v\\}\in\tbinom{V}{2}\setminus
E\mid\mathcal{P}[u]=\mathcal{P}[v]\\}\hskip 1.00006pt|+|\hskip
1.00006pt\\{\\{u,v\\}\in E\mid\mathcal{P}[u]\neq\mathcal{P}[v]\\}\hskip
1.00006pt|.$ (1)

Fair Correlation Clustering then is the task to find a partition into _fair_
sets that minimizes the Correlation Clustering cost. We emphasize that this is
the complete, unweighted, min-disagree form of Correlation Clustering. (It is
often called _complete_ because every pair of objects is either similar or
dissimilar but none is indifferent regarding the clustering. It is unweighted
as the (dis)similarity between two vertices is binary. A pair of similar
objects that are placed in separate clusters as well as a pair of dissimilar
objects in the same cluster is called a _disagreement_ , hence the naming of
the min-disagree form.)

There are two papers that appear to have started studying Fair Correlation
Clustering independently111Confusingly, they both carry the title _Fair
Correlation Clustering_.. Ahmadian, Epasto, Kumar, and Mahdian [2] analyze
settings where the fairness constraint is given by some $\alpha$ and require
that the ratio of each color in each cluster is at most $\alpha$. For
$\alpha=\frac{1}{2}$, which corresponds to our fairness definition if there
are two colors in a ratio of $1:1$, they obtain a 256-approximation. For
$\alpha=\frac{1}{k}$, where $k$ is the number of colors in the graph, they
give a $16.48k^{2}$-approximation. We note that all their variants are only
equivalent to our fairness notion if there are $\alpha^{-1}$ colors that all
occur equally often. Ahmadi, Galhotra, Saha, and Schwartz [1] give an
$\mathrm{O}{(c^{2}})$-approximation algorithm for instances with two colors in
a ratio of $1:c$. In the special case of a color ratio of $1:1$, they obtain a
$3\beta+4$-approximation, given any $\beta$-approximation to unfair
Correlation Clustering. With a more general color distribution, their approach
also worsens drastically. For instances with $k$ colors in a ratio of
$1:c_{2}:c_{3}:\ldots:c_{k}$ for positive integers $c_{i}$, they give an
$\mathrm{O}(k^{2}\cdot\max_{2\leqslant i\leqslant k}c_{i})$-approximation for
the strict, and an $\mathrm{O}(k^{2}\cdot\max_{2\leqslant i\leqslant
k}q_{i})$-approximation for the relaxed setting222Their theorem states they
achieve an $\mathrm{O}(\max_{2\leqslant i\leqslant k}q_{i})$-approximation but
when looking at the proof it seems they have accidentally forgotten the
$k^{2}$ factor..

Following these two papers, Friggstad and Mousavi [28] provide an
approximation to the $1:1$ color ratio case with a factor of $6.18$. To the
best of our knowledge, the most recent publication on Fair Correlation
Clustering is by Ahmadian and Negahbani [3] who give approximations for Fair
Correlation Clustering with a slightly different way of relaxing fairness.
They give an approximation with ratio
$\mathcal{O}(\varepsilon^{-1}k\max_{2\leqslant i\leqslant k}c_{i})$ for color
distribution $1:c_{2}:c_{3}:\ldots:c_{k}$, where $\varepsilon$ relates to the
amount of relaxation (roughly $q_{i}=(1+\epsilon)c_{i}$ for our definition of
relaxed fairness).

All these results for Fair Correlation Clustering seem to converge towards
considering the very restricted setting of two colors in a ratio of $1:1$ in
order to give some decent approximation ratio. In this paper, we want to
understand if this is unavoidable, or if there is hope to find better results
for other (possibly more realistic) color distributions. In order to isolate
the role of fairness, we consider “easy” instances for Correlation Clustering,
and study the increase in complexity when adding fairness constraints.
Correlation Clustering without the fairness constraint is easily solved on
forests. We find that Fair Correlation Clustering restricted to forests turns
NP-hard very quickly, even when additionally assuming constant degree or
diameter. Most surprisingly, this hardness essentially also holds for relaxed
fairness, showing that the hardness of the problem is not due to the
strictness of the fairness definition.

On the positive side, we identify color distributions that allow for efficient
algorithms. Not surprisingly, this includes ratio $1:1$, and extends to a
constant number of $k$ colors with distribution
$c_{1}:c_{2}:c_{3}:\ldots:c_{k}$ for constants $c_{1},\dots,c_{k}$. Such
distributions can be used to model sensitive attributes with a limited number
of manifestation that are almost evenly distributed. Less expected, we also
find tractability for, in a sense, the other extreme. We show that Fair
Correlation Clustering on forests can be solved in polynomial time for two
colors with ratio $1:c$ with $c$ being very large (linear in the number of
overall vertices). Such a distribution can be used to model a scenario where a
minority is drastically underrepresented and thus in dire need of fairness
constraints. Although our results only hold for forests, we believe that they
can offer a starting point for more general graph classes. We especially hope
that our work sparks interest in the so far neglected distribution of ratio
$1:c$ with $c$ being very large.

###  1.1 Related Work

The study of clustering objectives similar or identical to Correlation
Clustering dates back to the 1960s [10, 33, 37]. Bansal, Blum, and Chawla [8]
were the first to coin the term Correlation Clustering as a clustering
objective. We note that it is also studied under the name Cluster Editing. The
most general formulation of Correlation Clustering regarding weights considers
two positive real values for each pair of vertices, the first to be added to
the cost if the objects are placed in the same cluster and the second to be
added if the objects are placed in separate clusters [4]. The recent book by
Bonchi, García-Soriano, and Gullo [13] gives a broad overview of the current
research on Correlation Clustering.

We focus on the particular variant that considers a complete graph with
$\\{-1,1\\}$ edge-weights, and the min disagreement objective function. This
version is APX-hard [16], implying in particular that there is no algorithm
giving an arbitrarily good approximation unless $\textsf{P}=\textsf{NP}$. The
best known approximation for Correlation Clustering is the very recent
breakthrough by Cohen-Addad, Lee and Newman [20] who give a ratio of
$(1.994+\epsilon)$.

We show that in forests, all clusters of an optimal Correlation Clustering
solution have a fixed size. In such a case, Correlation Clustering is related
to $k$-Balanced Partitioning. There, the task is to partition the graph into
$k$ clusters of equal size while minimizing the number of edges that are cut
by the partition. Feldmann and Foschini [27] study this problem on trees and
their results have interesting parallels with ours.

Aside from the results on Fair Correlation Clustering already discussed above,
we are only aware of three papers that consider a fairness notion close to the
one of Chierichetti et al. [19] for a graph clustering objective. Schwartz and
Zats [35] consider incomplete Fair Correlation Clustering with the max-agree
objective function. Dinitz, Srinivasan, Tsepenekas, and Vullikanti [23] study
Fair Disaster Containment, a graph cut problem involving fairness. Their
problem is not directly a fair clustering problem since they only require one
part of their partition (the saved part) to be fair. Ziko, Yuan, Granger, and
Ayed [38] give a heuristic approach for fair clustering in general that
however does not allow for theoretical guarantees on the quality of the
solution.

##  2 Contribution

We now outline our findings on Fair Correlation Clustering. We start by giving
several structural results that underpin our further investigations.
Afterwards, we present our algorithms and hardness results for certain graph
classes and color ratios. We further show that the hardness of fair clustering
does _not_ stem from the requirement of the clusters exactly reproducing the
color distribution of the whole graph. This section is concluded by a
discussion of possible directions for further research.

###  2.1 Structural Insights

Figure 1: Example forest where a cluster of size 4 and two clusters of size 2
incur the same cost. With one cluster of size 4 (left), the inter-cluster cost
is 0 and the intra-cluster cost is 4. With two clusters of size 2 (right),
both the inter-cluster and intra-cluster cost are 2.

We outline here the structural insights that form the foundation of all our
results. We first give a close connection between the cost of a clustering,
the number of edges “cut” by a clustering, and the total number of edges in
the graph. We refer to this number of “cut” edges as the _inter-cluster_ cost
as opposed to the number of non-edges inside clusters, which we call the
_intra-cluster_ cost. Formally, the intra- and inter-cluster cost are the
first and second summand of the Correlation Clustering cost in Equation 1,
respectively. The following lemma shows that minimizing the inter-cluster cost
suffices to minimize the total cost if all clusters are of the same size. This
significantly simplifies the algorithm development for Correlation Clustering.

######  Lemma 2.1.

Let $\mathcal{P}$ be a partition of the vertices of an $m$-edge graph $G$. Let
$\chi$ denote the inter-cluster cost incurred by $\mathcal{P}$ on $G$. If all
sets in the partition are of size $d$, then
$\text{cost}(\mathcal{P})=\frac{(d-1)}{2}\hskip 1.00006ptn-m+2\chi$. In
particular, if $G$ is a tree, $\text{cost}(\mathcal{P})=\frac{(d-3)}{2}\hskip
1.00006ptn+2\chi+1$.

The condition that all clusters need to be of the same size seems rather
restrictive at first. However, we prove in the following that in bipartite
graphs and, in particular, in forests and trees there is always a minimum-cost
fair clustering such that indeed all clusters are equally large. This property
stems from how the fairness constraint acts on the distribution of colors and
is therefore specific to Fair Correlation Clustering. It allows us to fully
utilize 2.1 both for building reductions in NP-hardness proofs as well as for
algorithmic approaches as we can restrict our attention to partitions with
equal cluster sizes.

Consider two colors of ratio $1:2$, then any fair cluster must contain at
least 1 vertex of the first color and 2 vertices of the second color to fulfil
the fairness requirement. We show that a minimum-cost clustering of a forest,
due to the small number of edges, consists entirely of such minimal clusters.
Every clustering with larger clusters incurs a higher cost.

######  Lemma 2.2.

Let $F$ be a forest with $k\geqslant 2$ colors in a ratio of
$c_{1}:c_{2}:\ldots:c_{k}$ with $c_{i}\in\mathbb{N}_{>0}$ for all $i\in[k]$,
$\gcd(c_{1},c_{2},\ldots,c_{k})=1$, and $\sum_{i=1}^{k}c_{i}\geqslant 3$.
Then, all clusters of every minimum-cost fair clustering are of size
$d=\sum_{i=1}^{k}c_{i}$.

2.2 does not extend to two colors in a ratio of $1:1$ as illustrated in Figure
1. In fact, this color distribution is the only case for forests where a
partition with larger clusters can have the same (but no smaller) cost. We
prove a slightly weaker statement than 2.2, namely, that _there is_ always a
minimum-cost fair clustering whose cluster sizes are given by the color ratio.
We find that this property, in turn, holds not only for forests but for every
bipartite graph. Note that in general bipartite graphs there are more color
ratios than only $1:1$ that allow for these ambiguities.

######  Lemma 2.3.

Let $G=(A\cup B,E)$ be a bipartite graph with $k\geqslant 2$ colors in a ratio
of $c_{1}:c_{2}:\ldots:c_{k}$ with $c_{i}\in\mathbb{N}_{>0}$ for all $i\in[k]$
and $\gcd(c_{1},c_{2},\ldots,c_{k})=1$. Then, there is a minimum-cost fair
clustering such that all its clusters are of size $d=\sum_{i=1}^{k}c_{i}$.
Further, each minimum-cost fair clustering with larger clusters can be
transformed into a minimum-cost fair clustering such that all clusters contain
no more than $d$ vertices in linear time.

In summary, the results above show that the ratio of the color classes is the
key parameter determining the cluster size. If the input is a bipartite graph
whose vertices are colored with $k$ colors in a ratio of
$c_{1}:c_{2}:\dots:c_{k}$, our results imply that without loosing optimality,
solutions can be restricted to contain only clusters of size
$d=\sum_{i=1}^{k}c_{i}$, each with exactly $c_{i}$ vertices of color $i$.
Starting from these observations, we show in this work that the color ratio is
also the key parameter determining the complexity of Fair Correlation
Clustering. On the one hand, the simple structure of optimal solutions
restricts the search space and enables polynomial-time algorithms, at least
for some instances. On the other hand, these insights allow us to show
hardness already for very restricted input classes. The technical part of most
of the proofs consists of exploiting the connection between the clustering
cost, total number of edges, and the number of edges cut by a clustering.

###  2.2 Tractable Instances

Table 1: Running times of our algorithms for Fair Correlation Clustering on forests depending on the color ratio. Value $p$ is any rational such that $\nicefrac{{n}}{{p}}-1$ is integral; $c_{1},c_{2},\dots,c_{k}$ are coprime positive integers, possibly depending on $n$. Functions $f$ and $g$ are given in Theorems 6.12 and 6.19.  Color Ratio | $1:1$ | $1:2$ | $1:(\nicefrac{{n}}{{p}}\,{-}\,1)$ | $c_{1}:c_{2}:\ldots:c_{k}$
---|---|---|---|---
Running Time | $\mathrm{O}(n)$ | $\mathrm{O}(n^{6})$ | $\mathrm{O}\\!\left(n^{f(p)}\right)$ | $\mathrm{O}\\!\left(n^{g(c_{1},\dots,c_{k})}\right)$

We start by discussing the algorithmic results. The simplest case is that of
two colors, each one occurring equally often. We prove that for bipartite
graphs with a color ratio $1:1$ Fair Correlation Clustering is equivalent to
the maximum bipartite matching problem, namely, between the vertices of
different color. Via the standard reduction to computing maximum flows, this
allows us to benefit from the recent breakthrough by Chen, Kyng, Liu, Peng,
Probst Gutenberg, and Sachdeva [18]. It gives an algorithm running in time
$m^{1+o(1)}$.

The remaining results focus on forests as the input, see Table 1. It should
not come as a surprise that our main algorithmic paradigm is dynamic
programming. A textbook version finds a maximum matching in linear time in a
forests, solving the $1:1$ case. For general color ratios, we devise much more
intricate dynamic programs. We use the color ratio $1:2$ as an introductory
example. The algorithm has two phases. In the first, we compute a list of
candidate _splittings_ that partition the forest into connected parts
containing at most 1 blue and 2 red vertices each. In the second phase, we
assemble the parts of each of the splittings to fair clusters and return the
cheapest resulting clustering. The difficulty lies in the two phases not being
independent from each other. It is not enough to minimize the “cut” edges in
the two phases separately. We prove that the costs incurred by the merging
additionally depends on the number of of parts of a certain type generated in
the splittings. Tracking this along with the number of cuts results in a
$\mathrm{O}(n^{6})$-time algorithm. Note that we did not optimize the running
time as long as it is polynomial.

We generalize this to $k$ colors in a ratio $c_{1}:c_{2}:\dots:c_{k}$.333The
$c_{i}$ are coprime, but they are not necessarily constants with respect to
$n$.  We now have to consider _all_ possible colorings of a partition of the
vertices such that in each part the $i$-th color occurs at most $c_{i}$ times.
While assembling the parts, we have to take care that the merged colorings
remain compatible. The resulting running time is
$\mathrm{O}(n^{g(c_{1},\dots,c_{k})})$ for some (explicit) polynomial $g$.
Recall that, by 2.2, the minimum cluster size is $d=\sum_{i=1}^{k}c_{i}$. If
this is a constant, then the dynamic program runs in polynomial time. If,
however, the number of colors $k$ or some color’s proportion grows with $n$,
it becomes intractable. Equivalently, the running time gets worse if there are
very large but sublinearly many clusters.

To mitigate this effect, we give a complementary algorithm at least for
forests with two colors. Namely, consider the color ratio $1:\frac{n}{p}-1$.
Then, an optimal solution has $p$ clusters each of size
$d=\nicefrac{{n}}{{p}}$. The key observation is that the forest contains $p$
vertices of the color with fewer occurrences, say, blue, and any fair
clustering isolates the blue vertices. This can be done by cutting at most
$p-1$ edges and results in a collection of (sub-)trees where each one has at
most one blue vertex. To obtain the clustering, we split the trees with red
excess vertices and distribute those among the remaining parts. We track the
costs of all the $\mathrm{O}(n^{\textsf{poly}(p)})$ many cut-sets and
rearrangements to compute the one of minimum cost. In total, the algorithm
runs in time $\mathrm{O}(n^{f(p)})$ for some polynomial in $p$. In summary, we
find that if the number of clusters $p$ is constant, then the running time is
polynomial. Considering in particular an integral color ratio $1:c$,444 In a
color ratio $1:c$, $c$ is not necessarily a constant, but ratios like $2:5$
are not covered. , we find tractability for forests if $c=\mathrm{O}(1)$ or
$c=\mathrm{\Omega}(n)$. We will show next that Fair Correlation Clustering
with this kind of a color ratio is NP-hard already on trees, hence the
hardness must emerge somewhere for intermediate $c$.

###  2.3 A Dichotomy for Bounded Diameter

Table 2: Complexity of Fair Correlation Clustering on trees and general graphs depending on the diameter. The value $c$ is a positive integer, possibly depending on $n$. Diameter | Color Ratio | Trees | General Graphs
---|---|---|---
$2,3$ | any | $\mathrm{O}(n)$ |  NP-hard
$\geqslant 4$ | $1:c$ |  NP-hard |  NP-hard

Table 2 shows the complexity of Fair Correlation Clustering on graphs with
bounded diameter. We obtain a dichotomy for trees with two colors with ratio
$1:c$. If the diameter is at most $3$, an optimal clustering is computable in
$\mathrm{O}(n)$ time, but for diameter at least $4$, the problem becomes NP-
hard. In fact, the linear-time algorithm extends to trees with an arbitrary
number of colors in any ratio.

The main result in that direction is the hardness of Fair Correlation
Clustering already on trees with diameter at least 4 and two colors of ratio
$1:c$. This is proven by a reduction from the strongly NP-hard 3-Partition
problem. There, we are given positive integers $a_{1},\dots,a_{\ell}$ where
$\ell$ is a multiple of $3$ and there exists some $B$ with
$\sum_{i=1}^{\ell}a_{i}=B\cdot\frac{\ell}{3}$. The task is to partition the
numbers $a_{i}$ into triples such that each one of those sums to $B$. The
problem remains NP-hard if all the $a_{i}$ are strictly between
$\nicefrac{{B}}{{4}}$ and $\nicefrac{{B}}{{2}}$, ensuring that, if some subset
of the numbers sums to $B$, it contains exactly three elements.

We model this problem as an instance of Fair Correlation Clustering as
illustrated in Figure 2. We build $\ell$ stars, where the $i$-th one consists
of $a_{i}$ red vertices, and a single star of $\nicefrac{{\ell}}{{3}}$ blue
vertices. The centers of the blue star and all the red stars are connected.
The color ratio in the resulting instance is $1:B$. 2.2 then implies that
there is a minimum-costs clustering with $\nicefrac{{\ell}}{{3}}$ clusters,
each with a single blue vertex and $B$ red ones. We then apply 2.1 to show
that this cost is below a certain threshold if and only if each cluster
consist of exactly three red stars (and an arbitrary blue vertex), solving
3-Partition.

Figure 2: The tree with diameter 4 in the reduction from 3-Partition to Fair
Correlation Clustering.

###  2.4 Maximum Degree

The reduction above results in a tree with a low diameter but arbitrarily high
maximum degree. We have to adapt our reductions to show hardness also for
bounded degrees. The results are summarized in Table 3. If the Fair
Correlation Clustering instance is not required to be connected, we can
represent 3-Partition with a forest of trees with maximum degree $2$, that is,
a forest of paths. The input numbers are modeled by paths with $a_{i}$
vertices. The forest also contains $\nicefrac{{\ell}}{{3}}$ isolated blue
vertices, which again implies that an optimal fair clustering must have
$\nicefrac{{\ell}}{{3}}$ clusters each with $B$ red vertices. By defining a
sufficiently small cost threshold, we ensure that the fair clustering has cost
below it if and only if none of the path-edges are “cut” by the clustering,
corresponding to a partition of the $a_{i}$.

There is nothing special about paths, we can arbitrarily restrict the shape of
the trees, as long it is always possible to form such a tree with a given
number of vertices. However, the argument crucially relies on the absence of
edges between the $a_{i}$-paths/trees and does not transfer to connected
graphs. This is due to the close relation between inter-cluster costs and the
total number of edges stated in 2.1. The complexity of Fair Correlation
Clustering on a single path with a color ratio $1:c$ therefore remains open.
Notwithstanding, we show hardness for trees in two closely related settings:
keeping the color ratio at $1:c$ but raising the maximum degree to $5$, or
having a single path but a total of $\nicefrac{{n}}{{2}}$ colors and each
color shared by exactly $2$ vertices.

For the case of maximum degree $5$ and two colors with ratio $1:c$, we can
again build on the 3-Partition machinery. The construction is inspired by how
Feldmann and Foschini [27] used the problem to show hardness of computing so-
called $k$-balanced partitions. We adapt it to our setting in which the
vertices are colored and the clusters need to be fair.

For the single path with $\nicefrac{{n}}{{2}}$ colors, we reduce from (the
1-regular 2-colored variant of) the Paint Shop Problem for Words [24]. There,
a word is given in which every symbol appears exactly twice. The task is to
assign the values $0$ and $1$ to the letters of the word555The original
formulation [24] assigns colors, aligning better with the paint shop analogy.
We change the exposition here in order to avoid confusion with the colors in
the fairness sense.  such that that, for each symbol, exactly one of the two
occurrences receives a $1$, but the number of blocks of consecutive $0$s and
$1$s over the whole word is minimized. In the translation to Fair Correlation
Clustering, we represent the word as a path and the symbols as colors. To
remain fair, there must be two clusters containing exactly one vertex of each
color, translating back to a $0/1$-assignment to the word.

Table 3: Hardness of Fair Correlation Clustering on trees and forests depending on the maximum degree. The value $c$ is a positive integer, possibly depending on $n$. The complexity for paths (trees with maximum degree $2$) with color ratio $1:c$ is open. Max. Degree | Color Ratio | Trees | Forests
---|---|---|---
$2$ | $1:c$ |  |  NP-hard
$\geqslant 2$ |  |  $n/2$ colors,
---
2 vertices each
NP-hard |  NP-hard
$\geqslant 5$ | $1:c$ |  NP-hard |  NP-hard

###  2.5 Relaxed Fairness

One could think that the hardness of Fair Correlation Clustering already for
classes of trees and forests has its origin in the strict fairness condition.
After all, the color ratio in each cluster must precisely mirror that of the
whole graph. This impression is deceptive. Instead, we lift most of our
hardness results to Relaxed Fair Correlation Clustering considering the
_relaxed fairness_ of Bera et al. [11]. Recall 1.2. It prescribes two
rationals $p_{i}$ and $q_{i}$ for each color $i$ and allows, the proportion of
$i$-colored elements in any cluster to be in the interval $[p_{i},q_{i}]$,
instead of being precisely $\nicefrac{{c_{i}}}{{d}}$, where
$d=\sum_{j=1}^{k}c_{j}$.

The main conceptual idea is to show that, in some settings but not all, the
_minimum-cost_ solution under a relaxed fairness constraint is in fact
_exactly_ fair. This holds for the settings described above where we reduce
from 3-Partition. In particular, Relaxed Fair Correlation Clustering with a
color ratio of $1:c$ is NP-hard on trees with diameter $4$ and forests of
paths, respectively. Furthermore, the transferal of hardness is immediate for
the case of a single path with $\nicefrac{{n}}{{2}}$ colors and exactly $2$
vertices of each color. Any relaxation of fairness still requires one vertex
of each color in every cluster, maintaining the equivalence to the Paint Shop
Problem for Words.

In contrast, algorithmic results are more difficult to extend if there are
relaxedly fair solutions that have lower cost than any exactly fair one. We
then no longer know the cardinality of the clusters in an optimal solution. As
a proof of concept, we show that a slight adaption of our dynamic program for
two colors in a ratio of $1:1$ still works for what we call $\alpha$-_relaxed
fairness_.666This should not be confused with the notion of
$\alpha$_-fairness_ in resource allocation [30, 31].  There, the lower
fairness ratio is $p_{i}=\alpha\cdot\frac{c_{i}}{d}$ and the upper one is
$q_{i}=\frac{1}{\alpha}\cdot\frac{c_{i}}{d}$ for some parameter
$\alpha\in(0,1)$. We give an upper bound on the necessary cluster size
depending on $\alpha$, which is enough to find a good splitting of the forest.
Naturally, the running time now also depends on $\alpha$, but is of the form
$O(n^{h(1/\alpha)})$ for some polynomial $h$. In particular, we get an
polynomial-time algorithm for constant $\alpha$. The proof of correctness
consists of an exhaustive case distinction already for the simple case of
$1:1$. We are confident that this can be extended to more general color
ratios, but did not attempt it in this work.

###  2.6 Summary and Outlook

We show that Fair Correlation Clustering on trees, and thereby forests, is NP-
hard. It remains so on trees of constant degree or diameter, and–for certain
color distributions–it is also NP-hard on paths. On the other hand, we give a
polynomial-time algorithm if the minimum size $d$ of a fair cluster is
constant. We also provide an efficient algorithm for the color ratio $1:c$ if
the total number of clusters is constant, corresponding to $c\in\Theta(n)$.
For our main algorithms and hardness results, we prove that they still hold
when the fairness constraint is relaxed, so the hardness is not due to the
strict fairness definition. Ultimately, we hope that the insights gained from
these proofs as well as our proposed algorithms prove helpful to the future
development of algorithms to solve Fair Correlation Clustering on more general
graphs. In particular, fairness with color ratio $1:c$ with $c$ being very
large seems to be an interesting and potentially tractable type of
distribution for future study.

As first steps to generalize our results, we give a polynomial-time
approximation scheme (PTAS) for Fair Correlation Clustering on forests.
Another avenue for future research could be that 2.3, bounding the cluster
size of optimal solutions, extends also to bipartite graphs. This may prove
helpful in developing exact algorithms for bipartite graphs with other color
ratios than $1:1$.

Parameterized algorithms are yet another approach to solving more general
instances. When looking at the decision version of Fair Correlation
Clustering, our results can be cast as an XP-algorithm when the problem is
parameterized by the cluster size $d$, for it can be solved in time
$\mathrm{O}(n^{g(d)})$ for some function $g$. Similarly, we get an XP-
algorithm for the number of clusters as parameter. We wonder whether Fair
Correlation Clustering can be placed in the class FPT of fixed-parameter
tractable problems for any interesting structural parameters. This would
require a running time of, e.g., $g(d)\cdot\textsf{poly}(n)$. There are FPT-
algorithms for Cluster Editing parameterized by the cost of the solution [15].
Possibly, future research might provide similar results for the fair variant
as well. A natural extension of our dynamic programming approach could
potentially lead to an algorithm parameterizing by the treewidth of the input
graph. Such a solution would be surprising, however, since to the best of our
knowledge even for normal, unfair Correlation Clustering 777In more detail, no
algorithm for complete Correlation Clustering has been proposed. Xin [36]
gives a treewidth algorithm for _incomplete_ Correlation Clustering for the
treewidth of the graph of all positively and negatively labeled edges.  and
for the related Max Dense Graph Partition [22] no treewidth approaches are
known.

Finally, it is interesting how Fair Correlation Clustering behaves on paths.
While we obtain NP-hardness for a particular color distribution from the Paint
Shop Problem For Words, the question of whether Fair Correlation Clustering on
paths with for example two colors in a ratio of $1:c$ is efficiently solvable
or not is left open. However, we believe that this question is rather answered
by the study of the related (discrete) Necklace Splitting problem, see the
work of Alon and West [6]. There, the desired cardinality of every color class
is explicitly given, and it is non-constructively shown that there always
exists a split of the necklace with the number of cuts meeting the obvious
lower bound. A constructive splitting procedure may yield some insights for
Fair Correlation Clustering on paths.

##  3 Preliminaries

We fix here the notation we are using for the technical part and give the
formal definition of Fair Correlation Clustering.

###  3.1 Notation

We refer to the set of natural numbers $\\{0,1,2,\ldots\\}$ by $\mathbb{N}$.
For $k\in\mathbb{N}$, let $[k]=\\{1,2,\ldots,k\\}$ and
$\mathbb{N}_{>k}=\mathbb{N}\setminus\left(\\{0\\}\cup[k]\right)$. We write
$2^{[k]}$ for the power set of $[k]$. By $\gcd(a_{1},a_{2},\ldots,a_{k})$ we
denote the _greatest common divisor_ of
$a_{1},a_{2}\ldots,a_{k}\in\mathbb{N}$.

An _undirected graph_ $G=(V,E)$ is defined by a set of vertices $V$ and a set
of edges $E\subseteq\binom{V}{2}=\\{\\{u,v\\}\mid u,v\in V,u\neq v\\}$. If not
stated otherwise, by the _size of $G$_ we refer to $n+m$, where $n=|V|$ and
$m=|E|$. A graph is called _complete_ if $m=\frac{n(n-1)}{2}$. We call a graph
$G=(A\cup B,E)$ _bipartite_ if there are no edges in $A$ nor $B$, i.e.,
$E\cap\binom{A}{2}=E\cap\binom{B}{2}=\emptyset$. For every $S\subseteq V$, we
let $G[S]=\left(S,E\cap\binom{S}{2}\right)$ denote the _subgraph induced by
$S$_. The _degree_ of a vertex $v\in V$ is the number of edges incident to
that vertex, $\delta(v)=|\\{u\mid\\{u,v\\}\in E\\}|$. The _degree_ of a graph
$G=(V,E)$ is the maximum degree of any of its vertices $\delta(G)=\max_{v\in
V}\delta(v)$. A _path_ of length $k$ in $G$ is a tuple of vertices
$(v_{1},v_{2},\ldots,v_{k-1})$ such that for each $1\leqslant i<k-1$ we have
$\\{v_{i},v_{i+1}\\}\in E$. We only consider simple paths, i.e., we have
$v_{i}\neq v_{j}$ for all $i\neq j$. A graph is called _connected_ if for
every pair of vertices $u,v$ there is a path connecting $u$ and $v$. The
_distance_ between two vertices is the length of the shortest path connecting
these vertices and the _diameter_ of a graph is the maximum distance between a
pair of vertices. A _circle_ is a path $(v_{1},v_{2},\ldots,v_{k})$ such that
$v_{1}=v_{k}$ and $v_{i}\neq v_{j}$ only for all other pairs of $i\neq j$.

A _forest_ is a graph without circles. A connected forest is called a _tree_.
There is exactly one path connecting every pair of vertices in a tree. A tree
is _rooted_ by choosing any vertex $r\in V$ as the root. Then, every vertex
$v$, except for the root, has a _parent_ , which is the next vertex on the
path from $v$ to $r$. All vertices that have $v$ as a parent are referred to
as the _children_ of $v$. A vertex without children is called a _leaf_. Given
a rooted tree $T$, by $T_{v}$ we denote the subtree induced by $v$ and its
descendants, i.e., the set of vertices such that there is a path starting in
$v$ and ending in that vertex without using the edge to $v$’s parent. Observe
that each forest is a bipartite graph, for example by placing all vertices
with even distance to the root of their respective tree on one side and the
other vertices on the other side.

A finite set $U$ can be _colored_ by a function $c:U\rightarrow[k]$, for some
$k\in\mathbb{N}_{>0}$. If there are only two colors, i.e., $k=2$, for
convenience we call them _red_ and _blue_ , instead by numbers.

For a _partition_ $\mathcal{P}=\\{S_{1},S_{2},\ldots,S_{k}\\}$ with $S_{i}\cap
S_{j}=\emptyset$ for $i\neq j$ of some set $U=S_{1}\cup S_{2}\cup\ldots\cup
S_{k}$ and some $u\in U$ we use $\mathcal{P}[u]$ to refer to the set $S_{i}$
for which $u\in S_{i}$. Further, we define the term _coloring_ on sets and
partitions. The _coloring of a set_ counts the number of occurrences of each
color in the set.

######  Definition 3.1 (Coloring of Sets).

Let $S$ be a set colored by a function $c\colon S\rightarrow[k]$. Then, the
coloring of $S$ is an array $C_{S}$ such that $C_{S}[i]=|{\\{s\in S\mid
c(s)=i}\\}|$ for all $i\in[k]$.

The _coloring of a partition_ counts the number of occurrences of set
colorings in the partition.

######  Definition 3.2 (Coloring of Partitions).

Let $U$ be a colored set and let $\mathcal{P}$ be a partition of $U$. Let
$\mathcal{C}=\\{C_{S}\mid S\subseteq U\\}$ denote the set of set colorings for
which there is a subset of $U$ with that coloring. By an arbitrarily fixed
order, let $C_{1},C_{2},\ldots,C_{\ell}$ denote the elements of $\mathcal{C}$.
Then, the coloring of $\mathcal{P}$ is an array $C_{\mathcal{P}}$ such that
$C_{\mathcal{P}}[i]=|\\{S\in\mathcal{P}\mid C_{S}=C_{i}\\}|$ for all
$i\in[\ell]$.

###  3.2 Problem Definitions

In order to define Fair Correlation Clustering, we first give a formal
definition of the unfair clustering objective. Correlation Clustering receives
a pairwise similarity measure for a set of objects and aims at minimizing the
number of similar objects placed in separate clusters and the number of
dissimilar objects placed in the same cluster. For the sake of consistency, we
reformulate the definition of Bonchi et al. [13] such that the pairwise
similarity between objects is given by a graph rather than an explicit binary
similarity function. Given a graph $G=(V,E)$ and a partition $\mathcal{P}$ of
$V$, the Correlation Clustering cost is

$\displaystyle\text{cost}(G,\mathcal{P})=|\hskip
1.00006pt\\{\\{u,v\\}\in\tbinom{V}{2}\setminus
E\mid\mathcal{P}[u]=\mathcal{P}[v]\\}\hskip 1.00006pt|+|\hskip
1.00006pt\\{\\{u,v\\}\in E\mid\mathcal{P}[u]\neq\mathcal{P}[v]\\}\hskip
1.00006pt|.$

We refer to the first summand as the _intra-cluster cost_ $\psi$ and the
second summand as the _inter-cluster cost_ $\chi$. Where $G$ is clear from
context, we abbreviate to $\text{cost}(\mathcal{P})$. Sometimes, we consider
the cost of $\mathcal{P}$ on an induced subgraph. To this end, we allow the
same cost definition as above also if $\mathcal{P}$ partitions some set
$V^{\prime}\supseteq V$. We define (unfair) Correlation Clustering as follows.

Correlation Clustering
Input: Graph $G=(V,E)$. Task: Find a partition $\mathcal{P}$ of $V$ that
minimizes $\text{cost}(\mathcal{P})$.

We emphasize that this is the complete, unweighted, min-disagree form of
Correlation Clustering. It is complete as every pair of objects is either
similar or dissimilar but none is indifferent regarding the clustering. It is
unweighted as the (dis)similarity between two vertices is binary. A pair of
similar objects that are placed in separate clusters as well as a pair of
dissimilar objects in the same cluster is called a _disagreement_ , hence the
naming of the min-disagree form. An alternative formulation would be the max-
agree form with the objective to maximize the number of pairs that do not form
a disagreement. Note that both formulations induce the same ordering of
clusterings though approximation factors may differ because of the different
formulations of the cost function.

Our definition of the Fair Correlation Clustering problem loosely follows [2].
The fairness aspect limits the solution space to _fair_ partitions. A
partition is fair if each of its sets has the same color distribution as the
universe that is partitioned.

######  Definition 3.3 (Fair Subset).

Let $U$ be a finite set of elements colored by a function $c:U\rightarrow[k]$
for some $k\in\mathbb{N}_{>0}$. Let $U_{i}=\\{u\in U\mid c(u)=i\\}$ be the set
of elements of color $i$ for all $i\in[k]$. Then, some $S\subseteq U$ is fair
if and only if for all colors $i\in[k]$ we have $\frac{|S\cap
U_{i}|}{|S|}=\frac{|U_{i}|}{|U|}$.

######  Definition 3.4 (Fair Partition).

Let $U$ be a finite set of elements colored by a function $c:U\rightarrow[k]$
for some $k\in\mathbb{N}_{>0}$. Then, a partition $S_{1}\cup
S_{2}\cup\ldots\cup S_{\ell}=U$ is fair if and only if all sets
$S_{1},S_{2},\ldots,S_{\ell}$ are fair.

We now define complete, unweighted, min-disagree variant of the Fair
Correlation Clustering problem. When speaking of (Fair) Correlation
Clustering, we refer to this variant, unless explicitly stated otherwise.

Fair Correlation Clustering
Input: Graph $G=(V,E)$, coloring $c\colon V\rightarrow[k]$. Task: Find a fair
partition $\mathcal{P}$ of $V$ that minimizes $\text{cost}(\mathcal{P})$.

##  4 Structural Insights

We prove here the structural results outlined in subsection 2.1. The most
important insight is that in bipartite graphs, and in forests in particular,
there is always a minimum-cost fair clustering such that all clusters are of
some fixed size. This property is very useful, as it helps for building
reductions in hardness proofs as well as algorithmic approaches that enumerate
possible clusterings. Further, by the following lemma, this also implies that
minimizing the inter-cluster cost suffices to minimize the Correlation
Clustering cost, which simplifies the development of algorithms solving Fair
Correlation Clustering on such instances.

See 2.1

######  Proof 4.1.

Note that in each of the $\frac{n}{d}$ clusters there are $\frac{d(d-1)}{2}$
pairs of vertices, each incurring an intra-cost of 1 if not connected by an
edge. Let the total intra-cost be $\psi$. As there is a total of $m$ edges, we
have

$\displaystyle\text{cost}(\mathcal{P})=\chi+\psi=\chi+\frac{n}{d}\cdot\frac{d(d-1)}{2}-(m-\chi)=\frac{(d-1)n}{2}-m+2\chi.$

In particular, if $G$ is a tree, this yields
$\text{cost}(\mathcal{P})=\frac{(d-3)n}{2}+2\chi+1$ as there $m=n-1$.

###  4.1 Forests

We find that in forests in every minimum-cost partition all sets in the
partition are of the minimum size required to fulfill the fairness
requirement.

See 2.2

######  Proof 4.2.

Let $d=\sum_{i=1}^{k}c_{i}$. For any clustering $\mathcal{P}$ of $V$ to be
fair, all clusters must be at least of size $d$. We show that if there is a
cluster $S$ in the clustering with $|S|>d$, then we decrease the cost by
splitting $S$. First note that in order to fulfill the fairness constraint, we
have $|S|=ad$ for some $a\in\mathbb{N}_{\geqslant 2}$. Consider a new
clustering $\mathcal{P}^{\prime}$ obtained by splitting $S$ into
$S_{1},S_{2}$, where $S_{1}\subset S$ is an arbitrary fair subset of $S$ of
size $d$ and $S_{2}=S\setminus S_{1}$. Note that the cost incurred by every
edge and non-edge with at most one endpoint in $S$ is the same in both
clusterings. Let $\psi$ be the intra-cluster cost of $\mathcal{P}$ on $F[S]$.
Regarding the cost incurred by the edges and non-edges with both endpoints in
$S$, we know that

$\displaystyle\text{cost}(F[S],\mathcal{P})\geqslant\psi\geqslant\frac{ad(ad-1)}{2}-(ad-1)=\frac{a^{2}d^{2}-3ad+2}{2}$

since the cluster is of size $ad$ and as it is part of a forest it contains at
most $ad-1$ edges. In the worst case, the $\mathcal{P}^{\prime}$ cuts all the
$ad-1$ edges. However, we profit from the smaller cluster sizes. We have

$\displaystyle\text{cost}(F[S],\mathcal{P}^{\prime})=\chi+\psi$
$\displaystyle\leqslant ad-1+\frac{d(d-1)}{2}+\frac{(a-1)d\cdot((a-1)d-1)}{2}$
$\displaystyle=\frac{2d^{2}+a^{2}d^{2}-2ad^{2}+ad-2}{2}.$

Hence, $\mathcal{P}^{\prime}$ is cheaper by

$\displaystyle\text{cost}(F[S],\mathcal{P})-\text{cost}(F[S],\mathcal{P}^{\prime})\geqslant\frac{2ad^{2}-2d^{2}-4ad+4}{2}=ad(d-2)-d^{2}+2.$

This term is increasing in $a$. As $a\geqslant 2$, by plugging in $a=2$, we
hence obtain a lower bound of
$\text{cost}(F[S],\mathcal{P})-\text{cost}(F[S],\mathcal{P}^{\prime})\geqslant
d^{2}-4d+2$. For $d\geqslant 2$, the bound is increasing in $d$ and it is
positive for $d>3$. This means, if $d>3$ no clustering with a cluster of size
more than $d$ has minimal cost implying that all optimum clusterings only
consist of clusters of size $d$.

Last, we have to argue the case $d=3$, i.e., we have a color ratio of $1:2$ or
$1:1:1$. In this case $d^{2}-4d+2$ evaluates to $-1$. However, we obtain a
positive change if we do not split arbitrarily but keep at least one edge
uncut. Note that this means that one edge less is cut and one more edge is
present, which means that our upper bound on
$\text{cost}(T[S],\mathcal{P}^{\prime})$ decreases by 2, so $\mathcal{P}$ is
now cheaper. Hence, assume there is an edge $\\{u,v\\}$ such that $c(u)\neq
c(v)$. Then by splitting $S$ into $\\{u,v,w\\}$ and $S\setminus\\{u,v,w\\}$
for some vertex $w\in S\setminus\\{u,v\\}$ that makes the component
$\\{u,v,w\\}$ fair, we obtain a cheaper clustering. If there is no such edge
$\\{u,v\\}$, then $T[S]$ is not connected. This implies there are at most
$3a-3$ edges if the color ratio is $1:1:1$ since no edge connects vertices of
different colors and there are $a$ vertices of each color, each being
connected by at most $a-1$ edges due to the forest structure. By a similar
argument, there are at most $3a-2$ edges if the color ratio is $1:2$. Hence,
the lower bound on $\text{cost}(T[S],\mathcal{P})$ increases by 1. At the same
time, even if $\mathcal{P}^{\prime}$ cuts all edges it cuts at most $3a-2$
times, so it is at least 1 cheaper than anticipated. Hence, in this case
$\text{cost}(T[S],\mathcal{P}^{\prime})<\text{cost}(T[S],\mathcal{P})$ no
matter how we cut.

Note that Lemma 2.2 makes no statement about the case of two colors in a ratio
of $1:1$.

###  4.2 Bipartite Graphs

We are able to partially generalize our findings for trees to bipartite
graphs. We show that there is still always a minimum-cost fair clustering with
cluster sizes fixed by the color ratio. However, in bipartite graphs there may
also be minimum-cost clusterings with larger clusters. We start with the case
of two colors in a ratio of $1:1$ and then generalize to other ratios.

######  Lemma 4.3.

Let $G=(A\cup B,E)$ be a bipartite graph with two colors in a ratio of $1:1$.
Then, there is a minimum-cost fair clustering of $G$ that has no clusters with
more than 2 vertices. Further, each minimum-cost fair clustering can be
transformed into a minimum-cost fair clustering such that all clusters contain
no more than 2 vertices in linear time. If $G$ is a forest, then no cluster in
a minimum-cost fair clustering is of size more than 4.

######  Proof 4.4.

Note that, due to the fairness constraint, each fair clustering consists only
of evenly sized clusters. We prove both statements by showing that in each
cluster of at least 4 vertices there are always two vertices such that by
splitting them from the rest of the cluster the cost does not increase and
fairness remains.

Let $\mathcal{P}$ be a clustering and $S\in\mathcal{P}$ be a cluster with
$|S|\geqslant 4$. Let $S_{A}=S\cap A$ and $S_{B}=S\cap B$. Assume there is
$a\in S_{a}$ and $b\in S_{b}$ such that $a$ and $b$ have not the same color.
Then, the clustering $\mathcal{P}^{\prime}$ obtained by splitting $S$ into
$\\{a,b\\}$ and $S\setminus\\{a,b\\}$ is fair. We now analyze for each pair of
vertices $u,v,u\neq v$ how the incurred Correlation Clustering cost changes.
The cost does not change for every pair of vertices of which at most one
vertex of $u$ and $v$ is in $S$. Further, it does not change if either
$\\{u,v\\}=\\{a,b\\}$ or $\\{u,v\\}\subseteq S\setminus\\{a,b\\}$. There are
at most $|S_{A}|-1+|S_{B}|-1=|S|-2$ edges with one endpoint in $\\{a,b\\}$ and
the other in $S\setminus\\{a,b\\}$. Each of them is cut in
$\mathcal{P}^{\prime}$ but not in $\mathcal{P}$, so they incur an extra cost
of at most $|S|-2$. However, due to the bipartite structure, there are
$|S_{A}|-1$ vertices in $S\setminus\\{a,b\\}$ that have no edge to $a$ and
$|S_{B}|-1$ vertices in $S\setminus\\{a,b\\}$ that have no edge to $b$. These
$|S|-2$ vertices incur a total cost of $|S|-2$ in $\mathcal{P}$ but no cost in
$\mathcal{P}^{\prime}$. This makes up for any cut edge in $\mathcal{P}$, so
splitting the clustering never increases the cost.

If there is no $a\in S_{a}$ and $b\in S_{b}$ such that $a$ and $b$ have not
the same color, then either $S_{A}=\emptyset$ or $S_{B}=\emptyset$. In both
cases, there are no edges inside $S$, so splitting the clustering in an
arbitrary fair way never increases the cost.

By iteratively splitting large clusters in any fair clustering, we hence
eventually obtain a minimum-cost fair clustering such that all clusters
consist of exactly two vertices.

Now, assume $G$ is a forest and there would be a minimum-cost clustering
$\mathcal{P}$ with some cluster $S\in\mathcal{P}$ such that $|S|>2a$ for some
$a\in\mathbb{N}_{>2}$. Consider a new clustering $\mathcal{P}^{\prime}$
obtained by splitting $S$ into $\\{u,v\\}$ and $S\setminus\\{u,v\\}$, where
$u$ and $v$ are two arbitrary vertices of different color that have at most 1
edge towards another vertex in $S$. There are always two such vertices due to
the forest structure and because there are $\frac{S}{2}$ vertices of each
color. Then, $\mathcal{P}^{\prime}$ is still a fair clustering. Note that the
cost incurred by each edge and non-edge with at most one endpoint in $S$ is
the same in both clusterings. Let $\psi$ denote the intra-cluster cost of
$\mathcal{P}$ in $G[S]$. Regarding the edges and non-edges with both endpoints
in $S$, we know that

$\displaystyle\text{cost}(G[S],\mathcal{P})\geqslant\psi\geqslant\frac{2a(2a-1)}{2}-(2a-1)=2a^{2}-3a+1$

as the cluster consists of $2a$ vertices and has at most $2a-1$ edges due to
the forest structure. In the worst case, $\mathcal{P}^{\prime}$ cuts $2$
edges. However, we profit from the smaller cluster sizes. We have

$\displaystyle\text{cost}(G[S],\mathcal{P}^{\prime})\leqslant 2+\psi\leqslant
2+1+\frac{2(a-1)(2(a-1)-1)}{2}-(2a-1-2)=2a^{2}-5a+6.$

Hence, $\mathcal{P}$ costs at least $2a-5$ more than $\mathcal{P}^{\prime}$,
which is positive as $a>2$. Thus, in every minimum-cost fair clustering all
clusters are of size 4 or 2.

We employ an analogous strategy if there is a different color ratio than $1:1$
in the graph. However, then we have to split more than 2 vertices from a
cluster. To ensure that the clustering cost does not increase, we have to
argue that we can take these vertices in some balanced way from both sides of
the bipartite graph.

See 2.3

######  Proof 4.5.

Due to the fairness constraint, each fair clustering consists only of clusters
that are of size $ad$, where $a\in\mathbb{N}_{>0}$. We prove the statements by
showing that a cluster of size at least $2d$ can be split such that the cost
does not increase and fairness remains.

Let $\mathcal{P}$ be a clustering and $S\in\mathcal{P}$ be a cluster with
$|S|=ad$ for some $a\geqslant 2$. Let $S_{A}=S\cap A$ as well as $S_{B}=S\cap
B$ and w.l.o.g. $|S_{A}|\geqslant|S_{B}|$. Our proof has three steps.

  * •

First, we show that there is a fair $\widetilde{S}\subseteq S$ such that
$|\widetilde{S}|=d$ and $|\widetilde{S}\cap A|\geqslant|\widetilde{S}\cap B|$.

  * •

Then, we construct a fair set $\widehat{S}\subseteq S$ by replacing vertices
in $\widetilde{S}$ with vertices in $S_{B}\setminus\widetilde{S}$ such that
still $|\widehat{S}|=d,|\widehat{S}_{A}|\geqslant|\widehat{S}_{B}|$, with
$\widehat{S}_{A}=\widehat{S}\cap A$ and $\widehat{S}_{B}=\widehat{S}\cap B$,
and additionally $|\widehat{S}_{A}|-|\hat{S}_{B}|\leqslant|S_{A}|-|S_{B}|$.

  * •

Last, we prove that splitting $S$ into $\widehat{S}$ and
$S\setminus\widehat{S}$ does not increase the clustering cost.

We then observe that the resulting clustering is fair, so the lemma’s
statements hold because any fair clustering with a cluster of more than $d$
vertices is transformed into a fair clustering with at most the same cost, and
only clusters of size $d$ by repeatedly splitting larger clusters.

For the first step, assume there would be no such $\widetilde{S}\subseteq S$,
i.e., that we only could take $s<\frac{d}{2}$ vertices from $S_{A}$ without
taking more than $c_{i}$ vertices of each color $i\in[k]$. Let $s_{i}$ be the
number of vertices of color $i$ among these $s$ vertices for all $i\in[k]$.
Then, if $s_{i}=0$ there is no vertex of color $i$ in $S_{A}$ as we could take
the respective vertex into $\widetilde{S}$, otherwise. Analogously, if
$s_{i}<c_{i}$, then there are no more then $s_{i}$ vertices of color $i$ in
$S_{A}$. If we take $s_{i}=c_{i}$ vertices, then up to all of the
$ac_{i}=as_{i}$ vertices of that color are possibly in $S_{A}$. Hence,
$|S_{A}|\leqslant\sum_{i=1}^{k}as_{i}=as<\frac{ad}{2}$. This contradicts
$S_{A}\geqslant S_{B}$ because $|A|+|B|=ad$. Thus, there is a fair set
$\widetilde{S}$ of size $d$ such that $|\widetilde{S}\cap
S_{A}|\geqslant|\widetilde{S}\cap S_{B}|$.

Now, for the second step, we transform $\widetilde{S}$ into $\widehat{S}$.
Note that, if
$|S_{A}\setminus\widetilde{S}|\geqslant|S_{B}\setminus\widetilde{S}|$ it
suffices to set $\widehat{S}=\widetilde{S}$. Otherwise, we replace some
vertices from $\widetilde{S}\cap S_{A}$ by vertices of the respective color
from $S_{B}\setminus\widetilde{S}$. We have to show that after this we still
take at least as many vertices from $S_{A}$ as from $S_{B}$ and
$|S_{A}|-|\widehat{S}_{A}|\geqslant|S_{B}|-|\widehat{S}_{B}|$. Let

$\delta=|S_{B}\setminus\widetilde{S}|-|S_{A}\setminus\widetilde{S}|>0.$

Recall that $|S_{A}|\geqslant|S_{B}|$, so $\delta\leqslant|\widetilde{S}\cap
A|-|\widetilde{S}\cap B|$. Then, we build $\widehat{S}$ from $\widetilde{S}$
by replacing $\frac{\delta}{2}\leqslant\frac{d}{2}$ vertices from
$\widetilde{S}\cap S_{A}$ with vertices of the respective color from
$S_{B}\setminus\widetilde{S}$. If there are such $\frac{\delta}{2}$ vertices,
we have $|S_{A}\setminus\widehat{S}_{A}|=|S_{B}\setminus\widehat{S}_{B}|$ and
$|\widehat{S}_{A}|\geqslant|\widehat{S}_{B}|$. Consequently, $\widehat{S}$
fulfills the requirements.

Assume there would be no such $\frac{\delta}{2}$ vertices but that we could
only replace $s<\frac{\delta}{2}$ vertices. Let $s_{i}$ be the number of
vertices of color $i$ among these vertices for all $i\in[k]$. By a similar
argumentation as above and because there are only $(a-1)c_{i}$ vertices of
each color $i$ in $S\setminus\widehat{S}$, we have

$\displaystyle|S_{B}\setminus\widehat{S}|\leqslant\sum_{i=1}^{k}(a-1)s_{i}=(a-1)s<\frac{(a-1)d}{2}.$

This contradicts $|S_{B}\setminus\widetilde{S}|>|S_{A}\setminus\widetilde{S}|$
as $|(S_{A}\cup S_{B})\setminus\widetilde{S}|=(a-1)d$. Hence, there are always
enough vertices to create $\widehat{S}$.

For the last step, we show that splitting $S$ into $\widehat{S}$ and
$S\setminus\widehat{S}$ does not increase the cost by analyzing the change for
each pair of vertices $\\{u,v\\}\in\binom{V}{2}$. If not $u\in S$ and $v\in
S$, the pair is not affected. Further, it does not change if either
$\\{u,v\\}\subseteq\widehat{S}$ or
$\\{u,v\\}\subseteq(S\setminus\widehat{S})$. For the remaining pairs of
vertices, there are at most

$\displaystyle|\widehat{S}_{A}|\cdot|S_{B}\setminus\widehat{S}_{B}|+|\widehat{S}_{B}|\cdot|S_{A}\setminus\widehat{S}_{A}|=|\widehat{S}_{A}|\cdot|S_{B}|+|\widehat{S}_{B}|\cdot|S_{A}|-2\left(|\widehat{S}_{A}|\cdot|\widehat{S}_{B}|\right)$

edges that are cut when splitting $S$ into $\widehat{S}$ and
$S\setminus\widehat{S}$. At the same time, there are

$\displaystyle|\widehat{S}_{A}|\cdot|S_{A}\setminus\widehat{S}_{A}|+|\widehat{S}_{B}|\cdot|S_{B}\setminus\widehat{S}_{B}|=|\widehat{S}_{A}|\cdot|S_{A}|+|\widehat{S}_{B}|\cdot|S_{B}|-|\widehat{S}_{A}|^{2}-|\widehat{S}_{B}|^{2}$

pairs of vertices that are not connected and placed in separate clusters in
$\mathcal{P}^{\prime}$ but not in $\mathcal{P}$. Hence, we have $\mathcal{P}$
is more expansive than $\mathcal{P}^{\prime}$ by at least

$\displaystyle\text{cost}(\mathcal{P})-\text{cost}(\mathcal{P}^{\prime})$
$\displaystyle\geqslant|\widehat{S}_{A}|\cdot|S_{A}|+|\widehat{S}_{B}|\cdot|S_{B}|-|\widehat{S}_{A}|\cdot|S_{B}|-|\widehat{S}_{B}|\cdot|S_{A}|$
$\displaystyle\hphantom{{}\geqslant}-\left(|\widehat{S}_{A}|^{2}-2\left(|\widehat{S}_{A}|\cdot|\widehat{S}_{B}|\right)+|\widehat{S}_{B}|^{2}\right)$
$\displaystyle\geqslant\left(|\widehat{S}_{A}|-|\widehat{S}_{B}|\right)\cdot\left(|S_{A}|-|S_{B}|\right)-\left(|\widehat{S}_{A}|-|\widehat{S}_{B}|\right)^{2}.$

This is non-negative as $|\widehat{S}_{A}|\geqslant|\widehat{S}_{B}|$ and
$|\widehat{S}_{A}|-|\widehat{S}_{B}|\leqslant|S_{A}|-|S_{B}|$. Hence,
splitting a cluster like this never increases the cost.

Unlike in forests, however, the color ratio yields no bound on the maximum
cluster size in minimum-cost fair clusterings on bipartite graphs but just
states there is a minimum-cost fair clustering with bounded cluster size. Let
$G=(R\cup B,\\{\\{r,b\\}\mid r\in R\wedge b\in B\\})$ be a complete bipartite
graph with $|R|=|B|$ such that all vertices in $R$ are red and all vertices in
$B$ are blue. Then, all fair clusterings in $G$ have the same cost, including
the one with a single cluster $S=R\cup B$. This holds because of a similar
argument as employed in the last part of Lemma 4.3 since every edge that is
cut by a clustering is compensated for with exactly one pair of non-adjacent
vertices that is then no longer in the same cluster.

##  5 Hardness Results

This section provides NP-hardness proofs for Fair Correlation Clustering under
various restrictions.

###  5.1 Forests and Trees

With the knowledge of the fixed sizes of clusters in a minimum-cost
clustering, we are able to show that the problem is surprisingly hard, even
when limited to certain instances of forests and trees.

To prove the hardness of Fair Correlation Clustering under various
assumptions, we reduce from the strongly NP-complete 3-Partition problem [29].

3-Partition
Input: $n=3p$ with $p\in\mathbb{N}$, positive integers
$a_{1},a_{2},\ldots,a_{n}$, and $B\in\mathbb{N}$ such that
$\frac{B}{4}<a_{i}<\frac{B}{2}$ as well as $\sum_{i=1}^{n}a_{i}=pB$. Task:
Decide if there is a partition of the numbers $a_{i}$ into triples such that
the sum of each triple is $B$.

Our first reduction yields hardness for many forms of forests.

######  Theorem 5.1.

_Fair Correlation Clustering_ on forests with two colors in a ratio of $1:c$
is _NP_ -hard. It remains _NP_ -hard when arbitrarily restricting the shape of
the trees in the forest as long as for every $a\in\mathbb{N}$ it is possible
to form a tree with $a$ vertices.

######  Proof 5.2.

We reduce from 3-Partition. For every $a_{i}$, we construct an arbitrarily
shaped tree of $a_{i}$ red vertices. Further, we let there be $p$ isolated
blue vertices. Note that the ratio between blue and red vertices is $1:B$. We
now show that there is a fair clustering $\mathcal{P}$ such that

$\text{cost}(\mathcal{P})=p\cdot\frac{B(B+1)}{2}-p(B-3)$

if and only if the given instance is a yes-instance for 3-Partition.

If we have a yes-instance of 3-Partition, then there is a partition of the set
of trees into $p$ clusters of size $B$. By assigning the blue vertices
arbitrarily to one unique cluster each, we hence obtain a fair partition. As
there are no edges between the clusters and each cluster consists of $B+1$
vertices and $B-3$ edges, this partition has a cost of
$p\cdot\frac{B(B+1)}{2}-p(B-3)$.

For the other direction, assume there is a fair clustering of cost
$\frac{B(B+1)}{2}-p(B-3)$. By 2.2, each of the clusters consists of exactly
one blue and $B$ red vertices. Each cluster requires $\frac{B(B+1)}{2}$ edges,
but the graph has only $p(B-3)$ edges. The intra-cluster cost alone is hence
at least $p\cdot\frac{B(B+1)}{2}-p(B-3p)$. This means that the inter-cluster
cost is 0, i.e., the partition does not cut any edges inside the trees. Since
all trees are of size greater than $\frac{B}{4}$ and less than $\frac{B}{2}$,
this implies that each cluster consists of exactly one blue vertex and exactly
three uncut trees with a total of $B$ vertices. This way, such a clustering
gives a solution to 3-Partition, so our instance is a yes-instance.

As the construction of the graph only takes polynomial time in the instance
size, this implies our hardness result.

Note that the hardness holds in particular for forests of paths, i.e., for
forests with maximum degree 2.

With the next theorem, we adjust the proof of Theorem 5.1 to show that the
hardness remains if the graph is connected.

######  Theorem 5.3.

_Fair Correlation Clustering_ on trees with diameter 4 and two colors in a
ratio of $1:c$ is _NP_ -hard.

######  Proof 5.4.

We reduce from 3-Partition. For every $a_{i}$, we construct a star of $a_{i}$
red vertices. Further, we let there be a star of $p$ blue vertices. We obtain
a tree of diameter 4 by connecting the center $v$ of the blue star to all the
centers of the red stars. The construction is depicted in Figure 3.

Figure 3: The tree with diameter 4 in the reduction from 3-Partition to Fair
Correlation Clustering. The notation follows that of Theorem 5.3.

Note that the ratio between blue and red vertices is $1:B$. We now show that
there is a fair clustering $\mathcal{P}$ such that

$\displaystyle\text{cost}(\mathcal{P})\leqslant\frac{pB^{2}-pB}{2}+7p-7$

if and only if the given instance is a yes-instance for 3-Partition.

If we have a yes-instance of 3-Partition, then there is a partition of the set
of stars into $p$ clusters of size $B$, each consisting of three stars. By
assigning the blue vertices arbitrarily to one unique cluster each, we hence
obtain a fair partition. We first compute the inter-cluster cost $\chi$. We
call an edge _blue_ or _red_ if it connects two blue or red vertices,
respectively. We call an edge _blue-red_ if it connects a blue and a red
vertex. All $p-1$ blue edges are cut. Further, all edges between $v$ (the
center of the blue star) and red vertices are cut except for the three stars
to which $v$ is assigned. This causes $3p-3$ more cuts, so the inter-cluster
cost is $\chi=4p-4$. Each cluster consists of $B+1$ vertices and $B-3$ edges,
except for the one containing $v$ which has $B$ edges. The intra-cluster cost
is hence

$\displaystyle\psi=p\left(\frac{B(B+1)}{2}-B+3\right)-3=\frac{pB^{2}-pB}{2}+3p-3.$

Combining the intra- and inter-cluster costs yields the desired cost of

$\displaystyle\text{cost}(\mathcal{P})=\chi+\psi=\frac{pB^{2}-pB}{2}+7p-7.$

For the other direction, assume there is a fair clustering of cost at most
$\frac{pB^{2}-pB}{2}+7p-7$. As there are $p(B+1)$ vertices, 2.2 gives that
there are exactly $p$ clusters, each consisting of exactly one blue and $B$
red vertices. Let $a$ denote the number of red center vertices in the cluster
of $v$. We show that $a=3$. To this end, let $\chi_{r}$ denote the number of
cut red edges. We additionally cut $p-1$ blue and $3p-a$ blue-red edges. The
inter-cluster cost of the clustering hence is $\chi=\chi_{r}+4p-a-1$.
Regarding the intra-cluster cost, there are no missing blue edges and as $v$
is the only blue vertex with blue-red edges, there are $(p-1)B+B-a=pB-a$
missing blue-red edges. Last, we require $p\cdot\frac{B(B-1)}{2}$ red edges,
but the graph has only $pB-3p$ red edges and $\chi_{r}$ of them are cut.
Hence, there are at least $p\cdot\frac{B(B-1)}{2}-pB+3p+\chi_{r}$ missing red
edges, resulting in a total intra-cluster cost of $\psi\geqslant
p\cdot\frac{B(B-1)}{2}+3p+\chi_{r}-a$. This results in a total cost of

$\displaystyle\text{cost}(\mathcal{P})=\chi+\psi\geqslant\frac{pB^{2}-pB}{2}+7p+2\chi_{r}-2a-1.$

As we assumed $\text{cost}(\mathcal{P})\leqslant\frac{pB^{2}-pB}{2}+7p-7$, we
have $2\chi_{r}-2a+6\leqslant 0$, which implies $a\geqslant 3$ since
$\chi_{r}\geqslant 0$. Additionally, $\chi_{r}\geqslant\frac{aB}{4}-(B-a)$,
because there are at least $\frac{B}{4}$ red vertices connected to each of the
$a$ chosen red centers but only a total of $B-a$ of them can be placed in
their center’s cluster. Thus, we have
$\frac{aB}{2}-2B+6=\frac{(a-4)B}{2}+6\leqslant 0$, implying $a<4$ and proving
our claim of $a=3$. Further, as $a=3$, we obtain $\chi_{r}\leqslant 0$,
meaning that no red edges are cut, so each red star is completely contained in
a cluster. Given that every red star is of size at least $\frac{B}{4}$ and at
most $\frac{B}{2}$, this means each cluster consists of exactly three complete
red stars with a total number of $B$ red vertices each and hence yields a
solution to the 3-Partition instance.

As the construction of the graph only takes polynomial time in the instance
size and the constructed tree is of diameter 4, this implies our hardness
result.

The proofs of Theorems 5.1 and 5.3 follow the same idea as the hardness proof
of [27, Theorem 2], which also reduces from 3-Partition to prove a hardness
result on the $k$-Balanced Partitioning problem. There, the task is to
partition the vertices of an uncolored graph into $k$ clusters of equal size
[27].

$k$-Balanced Partitioning
Input: Graph $G=(V,E)$, $k\in[n]$. Task: Find a partition $\mathcal{P}$ of $V$
that minimizes $|\\{\\{u,v\\}\in E\mid\mathcal{P}[u]\neq\mathcal{P}[v]\\}|$
under the constraint that $|\mathcal{P}|=k$ and
$|S|\leqslant\lceil\frac{n}{k}\rceil$ for all $S\in\mathcal{P}$ .

$k$-Balanced Partitioning is related to Fair Correlation Clustering on forests
in the sense that the clustering has to partition the forest into clusters of
equal sizes by Lemmas 2.2 and 4.3. Hence, on forests we can regard Fair
Correlation Clustering as the fair variant of $k$-Balanced Partitioning. By
[27, Theorem 8], $k$-Balanced Partitioning is NP-hard on trees of degree 5. In
their proof, Feldmann and Foschini [27] reduce from 3-Partition. We slightly
adapt their construction to transfer the result to Fair Correlation
Clustering.

######  Theorem 5.5.

_Fair Correlation Clustering_ on trees of degree at most 5 with two colors in
a ratio of $1:c$ is _NP_ -hard.

######  Proof 5.6.

We reduce from 3-Partition, which remains strongly NP-hard when limited to
instances where $B$ is a multiple of 4 since for every instance we can create
an equivalent instance by multiplying all integers by 4. Hence, assume a
3-Partition instance such that $B$ is a multiple of $4$. We construct a graph
for Fair Correlation Clustering by representing each $a_{i}$ for $i\in[n]$ by
a gadget $T_{i}$. Each gadget has a center vertex that is connected to the end
of five paths: one path of length $a_{i}$, three paths of length
$\frac{B}{4}$, and one path of length $\frac{B}{4}-1$. Then, for $i\in[n-1]$,
we connect the dangling ends of the paths of length $\frac{B}{4}-1$ in the
gadgets $T_{i}$ and $T_{i+1}$ by an edge. So far, the construction is similar
to the one by Feldmann and Foschini [27]. We color all vertices added so far
in red. Then, we add a path of $\frac{4n}{3}$ blue vertices and connect it by
an edge to an arbitrary vertex of degree 1. The resulting graph is depicted in
Figure 4.

Figure 4: Tree with maximum degree 5 in the reduction from 3-Partition to Fair
Correlation Clustering (Theorem 5.5).

Note that the construction takes polynomial time and we obtain a graph of
degree 5. We now prove that it has a fair clustering $\mathcal{P}$ such that

$\text{cost}(\mathcal{P})\leqslant\frac{(B-2)n}{2}+\frac{20n}{3}-3$

if and only if the given instance is a yes-instance for 3-Partition.

Assume we have a yes-instance for 3-Partition. We cut the edges connecting the
different gadgets as well as the edges connecting the $a_{i}$-paths to the
center of the stars. Then, we have $n$ components of size $B$ and 1 component
of size $a_{i}$ for each $i\in[n]$. The latter ones can be merged into
$p=\frac{n}{3}$ clusters of size $B$ without further cuts. Next, we cut all
edges between the blue vertices and assign one blue vertex to each cluster.
Thereby, note that the blue vertex that is already connected to a red cluster
should be assigned to this cluster. This way, we obtain a fair clustering with
inter-cluster cost $\chi=n-1+n+\frac{4n}{3}-1=\frac{10n}{3}-2$, which, by 2.1,
gives $\text{cost}(\mathcal{P})=\frac{(B-2)n}{2}+\frac{20n}{3}-3$.

For the other direction, let there be a minimum-cost fair clustering
$\mathcal{P}$ of cost at most $\frac{(B-2)n}{2}+\frac{20n}{3}-3$. As
$\sum_{i=1}^{n}a_{i}=\frac{nB}{3}$, the graph consists of $\frac{4n}{3}\cdot
B$ red and $\frac{4n}{3}$ blue vertices. By 2.2, $\mathcal{P}$ hence consists
of $\frac{4n}{3}$ clusters, each consisting of one blue vertex and $B$ red
vertices. Thus, $\mathcal{P}$ has to cut the $\frac{4n}{3}-1$ edges on the
blue path. Also, $\mathcal{P}$ has to partition the red vertices into sets of
size $B$. By [27, Lemma 9] this requires at least $2n-1$ cuts. This bounds the
inter-cluster cost by $\chi\geqslant 2n-1+\frac{4n}{3}-1=\frac{10n}{3}-2$,
leading to a Correlation Clustering cost of $\frac{(B-2)n}{2}+\frac{20n}{3}-3$
as seen above, so we know that no more edges are cut. Further, the unique
minimum-sized set of edges that upon removal leaves no red components of size
larger than $B$ is the set of the $n-1$ edges connecting the gadgets and the
$n$ edges connecting the $a_{i}$ paths to the center vertices [27, Lemma 9].
Hence, $\mathcal{P}$ has to cut exactly these edges. As no other edges are
cut, the $a_{i}$ paths can be combined to clusters of size $B$ without further
cuts, so the given instance has to be a yes-instance for 3-Partition.

###  5.2 Paths

Theorem 5.1 yields that Fair Correlation Clustering is NP-hard even in a
forest of paths. The problem when limited to instances of a single connected
path is closely related to the Necklace Splitting problem [5, 6].

Discrete Necklace Splitting
Input: Opened necklace $N$, represented by a path of $n\cdot k$ beads, each in
one of $t$ colors such that for each color $i$ there are $a_{i}\cdot k$ beads
of that color for some $a_{i}\in\mathbb{N}$. Task: Cut the necklace such that
the resulting intervals can be partitioned into $k$ collections, each
containing the same number of beads of each color.

The only difference to Fair Correlation Clustering on paths, other than the
naming, is that the number of clusters $k$ is explicitly given. From Lemmas
2.2 and 4.3 we are implicitly given this value also for Fair Correlation
Clustering, though. However, Alon and West [6] do not constructively minimize
the number of cuts required for a fair partition but non-constructively prove
that there is always a partition of at most $(k-1)\cdot t$ cuts, if there are
$t$ colors and the partition is required to consist of exactly $k$ sets with
the same amount of vertices of each color. Thus, it does not directly help us
when solving the optimization problem.

Moreover, Fair Correlation Clustering on paths is related to the 1-regular
2-colored variant of the Paint Shop Problem for Words (PPW). For PPW, a word
is given as well as a set of colors, and for each symbol and color a
requirement of how many such symbols should be colored accordingly. The task
is to find a coloring that fulfills all requirements and minimizes the number
of color changes between adjacent letters [24].

Paint Shop Problem for Words (PPW)
Input: Word $w=w_{1},w_{2},\ldots,w_{n}\in\Sigma^{*}$, number of colors
$k\in\mathbb{N}_{>0}$, and requirement function
$r:\Sigma\times[k]\rightarrow\mathbb{N}$ such that for each symbol $s$ used in
$w$ with $w[s]$ occurrences we have $\sum_{i=1}^{k}r(s,i)=w[s]$. Task: Find an
assignment function $f\colon[n]\rightarrow[k]$ of colors to the letters in $w$
such that for each symbol $s\in\Sigma$ and color $i\in[k]$ the coloring
fulfills the requirement function, i.e., $|\\{j\in[n]\mid w_{j}=s\wedge
f(j)=i\\}|=r(s,i)$. The assignment $f$ should minimze the number of color
changes $|\\{j\in[n-1]\mid f(j)\neq f(j+1)\\}|$.

Let for example $w=aabab$ and $r(a,1)=2,r(a,2)=r(b,1)=r(b,2)=1$. Then, the
assignment $f$ with $f(1)=f(2)=f(3)=1$ and $f(4)=f(5)=2$ fulfills the
requirement and has 1 color change.

PPW instances with a word containing every symbol exactly twice and two PPW-
colors, each requiring one of each symbol, are called _1-regular 2-colored_
and are shown to be NP-hard and even APX-hard [14]. With this, we prove NP-
hardness of Fair Correlation Clustering even on paths.

######  Theorem 5.7.

_Fair Correlation Clustering_ on paths is _NP -hard_, even when limited to
instances with exactly 2 vertices of each color.

######  Proof 5.8.

We reduce from 1-regular 2-colored PPW. Let $w=s_{1}s_{2},\ldots,s_{\ell}$. We
represent the $\frac{\ell}{2}$ different symbols by $\frac{\ell}{2}$ colors
and construct a path of length $\ell$, where each type of symbol is
represented by a unique color. By 2.2, any optimum Fair Correlation Clustering
solution partitions the paths into two clusters, each containing every color
exactly once, while minimizing the number of cuts (the inter-cluster cost) by
2.1. As this is exactly equivalent to assigning the letters in the word to one
of two colors and minimizing the number of color changes, we obtain our
hardness result.

APX-hardness however is not transferred since though there is a relationship
between the number of cuts (the inter-cluster cost) and the Correlation
Clustering cost, the two measures are not identical. In fact, as Fair
Correlation Clustering has a PTAS on forests by Theorem 8.4, APX-hardness on
paths would imply $\textsf{P}=\textsf{NP}$.

On a side note, observe that for every Fair Correlation Clustering instance on
paths we can construct an equivalent PPW instance (though not all of them are
1-regular 2-colored) by representing symbols by colors and PPW-colors by
clusters.

We note that it may be possible to efficiently solve Fair Correlation
Clustering on paths if there are e.g. only two colors. There is an NP-hardness
result on PPW with just two letters in [24], but a reduction from these
instances is not as easy as above since its requirements imply an unfair
clustering.

###  5.3 Beyond Trees

By Theorem 5.3, Fair Correlation Clustering is NP-hard even on trees with
diameter 4. Here, we show that if we allow the graph to contain circles, the
problem is already NP-hard for diameter 2. Also, this nicely contrasts that
Fair Correlation Clustering is solved on trees of diameter 2 in linear time,
as we will see in subsection 6.1.

######  Theorem 5.9.

_Fair Correlation Clustering_ on graphs of diameter 2 with two colors in a
ratio of $1:1$ is _NP_ -hard.

######  Proof 5.10.

Cluster Editing, which is an alternative formulation of Correlation
Clustering, is NP-hard on graphs of diameter 2 [9]. Further, Ahmadi et al. [1]
give a reduction from Correlation Clustering to Fair Correlation Clustering
with a color ratio of $1:1$. They show that one can solve Correlation
Clustering on a graph $G=(V,E)$ by solving Fair Correlation Clustering on the
graph $G^{\prime}=(V\cup V^{\prime},E\cup E^{\prime}\cup\widetilde{E})$ that
mirrors $G$. The vertices in $V$ are colored blue and the vertices in
$V^{\prime}$ are colored red. Formally, $V^{\prime}=\\{u^{\prime}\mid u\in
V\\}$ and $E^{\prime}=\\{\\{u^{\prime},v^{\prime}\\}\mid\\{u,v\\}\in E\\}$.
Further, $\widetilde{E}$ connects every vertex with its mirrored vertex as
well as the mirrors of adjacent vertices, i.e.,
$\widetilde{E}=\\{\\{u,u^{\prime}\\}\mid u\in
V\\}\cup\\{\\{u,v^{\prime}\\}\mid u\in V\wedge v^{\prime}\in
V^{\prime}\wedge\\{u,v\\}\in E\\}$, see Figure 5.

Figure 5: Graph as constructed by Ahmadi et al. [1] for the reduction from
Correlation Clustering to Fair Correlation Clustering. The blue vertices and
edges correspond to the original graph $G=(V,E)$, red vertices and edges to
its mirror, i.e., $V^{\prime}$ and $E^{\prime}$, and black edges to
$\widetilde{E}$.

Observe that if $G$ has diameter 2 then $G^{\prime}$ also has diameter 2 as
follows. As every pair of vertices $\\{u,v\\}\in\binom{V}{2}$ is of maximum
distance 2 and the vertices as well as the edges of $G$ are mirrored, every
pair of vertices $\\{u^{\prime},v^{\prime}\\}\in\binom{V^{\prime}}{2}$ is of
maximum distance 2. Further, every vertex and its mirrored vertex have a
distance of 1. For every pair of vertices $u\in V,v^{\prime}\in V^{\prime}$ we
distinguish two cases. If $\\{u,v\\}\in E$, then
$\\{u,v^{\prime}\\}\in\widetilde{E}$, so the distance is 1. Otherwise, as the
distance between $u$ and $v$ is at most 2 in $G$, there is $w\in V$ such that
$\\{u,w\\}\in E$ and $\\{v,w\\}\in E$. Thus,
$\\{u,w^{\prime}\\}\in\widetilde{E}$ and $\\{w^{\prime},v^{\prime}\\}\in
E^{\prime}$, so the distance of $u$ and $v^{\prime}$ is at most 2.

As Correlation Clustering on graphs with diameter 2 is NP-hard and the
reduction by Ahmadi et al. [1] constructs a graph of diameter 2 if the input
graph is of diameter 2, we have proven the statement.

Further, we show that on general graphs Fair Correlation Clustering is NP-
hard, even if the colors of the vertices allow for no more than 2 clusters in
any fair clustering. This contrasts our algorithm in subsection 6.4 solving
Fair Correlation Clustering on forests in polynomial time if the maximum
number of clusters is constant. To this end, we reduce from the NP-hard
Bisection problem [29], which is the $k=2$ case of $k$-Balanced Partitioning.

Bisection
Input: Graph $G=(V,E)$. Task: Find a partition $\mathcal{P}=\\{A,B\\}$ of $V$
that minimizes $|\\{\\{u,v\\}\in E\mid u\in A\wedge v\in B\\}|$ under the
constraint that $|A|=|B|$.

######  Theorem 5.11.

_Fair Correlation Clustering_ on graphs with two colors in a ratio of $1:c$ is
_NP_ -hard, even if $c=\frac{n}{2}-1$ and the graph is connected.

######  Proof 5.12.

We reduce from Bisection. Let $G=(V,E)$ be a Bisection instance and assume it
has an even number of vertices (otherwise it is a trivial no-instance). The
idea is to color all of the vertices in $V$ red and add two cliques, each
consisting of one blue and $|V|$ red vertices to enforce that a minimum-cost
Fair Correlation Clustering consists of exactly two clusters and thereby
partitions the vertices of the original graph in a minimum-cost bisection. The
color ratio is $2:3|V|$ which equals $1:\frac{|V^{\prime}|}{2}-1$ with
$V^{\prime}$ being the set of the newly constructed graph. We have to rule out
the possibility that a minimum-cost Fair Correlation Clustering is just one
cluster containing the whole graph. We do this by connecting the new blue
vertices $v_{1},v_{2}$ to only one arbitrary red vertex $v\in V$. We
illustrate the scheme in Figure 6.

Figure 6: Graph constructed for the reduction from Bisection to a Fair
Correlation Clustering instance with just 2 large clusters. The middle part
corresponds to the input graph $G$ and is colored red. $Clique_{1}$ and
$Clique_{2}$ are both cliques of $|V|$ red vertices and one blue vertex each.

We first argue that every clustering with two clusters is cheaper than placing
all vertices in the same cluster. Let $n=|V|$ as well as $m=|E|$. Let
$\mathcal{P}$ be a clustering that places all vertices in a single cluster.
Then,

$\displaystyle\text{cost}(\mathcal{P})=\frac{(3n+2)(3n+1)}{2}-\left(m+2+2\cdot\frac{n(n+1)}{2}\right)=\frac{7n^{2}}{2}+\frac{7n}{2}-m-1,$

as the cluster is of size $3n+2$, there is a total of $m+2$ plus the edges of
the cliques, and no edge is cut. Now assume we have a clustering
$\mathcal{P}^{\prime}$ with an inter-cluster cost of $\chi^{\prime}$ that puts
each clique in a different cluster. Then,

$\displaystyle\text{cost}(\mathcal{P}^{\prime})$
$\displaystyle=\chi^{\prime}+2\cdot\frac{(\frac{3n}{2}+1)(\frac{3n}{2})}{2}-\left(m-\chi^{\prime}+\frac{n(n+1)}{2}\right)$
$\displaystyle=\frac{7n^{2}}{4}+n-m+2\chi^{\prime}\leqslant\frac{9n^{2}}{4}+n-m+2,$

since there are at most $\frac{n}{2}\cdot\frac{n}{2}$ inter-cluster edges
between vertices of $V$ and one inter-cluster edge from $v$ to either $v_{1}$
or $v_{2}$, so $\chi\leqslant\frac{n^{2}}{4}+1$. Placing all vertices in the
same cluster is hence more expensive by

$\displaystyle\text{cost}(\mathcal{P})-\text{cost}(\mathcal{P}^{\prime})\geqslant\frac{7n^{2}}{2}+\frac{7n}{2}-m-1-\left(\frac{9n^{2}}{4}+n-m+2\right)=\frac{5n^{2}}{4}+\frac{5n}{2}-3$

than any clustering with two clusters. This is positive for $n\geqslant 2$.
Thus, Fair Correlation Clustering will always return at least two clusters.
Also, due to the fairness constraint and there being only two blue vertices,
it creates exactly two clusters.

Further, it does not cut vertices from one of the two cliques for the
following reason. As the clusters are of fixed size, by 2.1 we can focus on
the inter-cluster cost to argue that a minimum-cost Fair Correlation
Clustering only cuts edges in $E$. First, note that it is never optimal to cut
vertices from both cliques as just cutting the difference from one clique cuts
fewer edges. This also implies that at most $\frac{n}{2}$ red vertices are cut
from the clique as otherwise, the other cluster would have more than the
required $\frac{3n}{2}$ red vertices. So, assume $0<a\leqslant\frac{n}{2}$ red
vertices are cut from one clique. Any such solution has an inter-cluster cost
of $a\cdot(n+1-a)+\chi_{E}$, where $\chi_{E}$ is the number of edges in $E$
that are cut to split $V$ into two clusters of size $\frac{n}{2}+a$ and
$\frac{n}{2}-a$ as required to make a fair partition. We note that by not
cutting the cliques and instead cutting off $a$ vertices from the cluster of
size $\frac{n}{2}+a$, we obtain at most $a\cdot\frac{n}{2}+\chi_{E}$ cuts. As
$\frac{n}{2}<n+1-a$, this implies that no optimal solution cuts the cliques.
Hence, each optimal solution partitions the $V$ in a minimum-cost bisection.

Thus, by solving Fair Correlation Clustering on the constructed graph we can
solve Bisection in $G$. As further, the constructed graph is of polynomial
size in $|V|$, we obtain our hardness result.

##  6 Algorithms

The results from section 5 make it unlikely that there is a general polynomial
time algorithm solving Fair Correlation Clustering on trees and forests.
However, we are able to give efficient algorithms for certain classes of
instances.

###  6.1 Simple Cases

First, we observe that Fair Correlation Clustering on bipartite graphs is
equivalent to the problem of computing a maximum bipartite matching if there
are just two colors that occur equally often. This is due to there being a
minimum-cost fair clustering such that each cluster is of size 2.

######  Theorem 6.1.

Computing a minimum-cost fair clustering with two colors in a ratio of $1:1$
is equivalent to the maximum bipartite matching problem under linear-time
reductions, provided that the input graph has a minimum-cost fair clustering
in which each cluster has cardinality at most $2$.

######  Proof 6.2.

Let the colors be red and blue. By assumption, there is an optimum clustering
for which all clusters are of size at most 2. Due to the fairness constraint,
each such cluster consists of exactly 1 red and 1 blue vertex. By 2.1, the
lowest cost is achieved by the lowest inter-cluster cost, i.e., when the
number of clusters where there is an edge between the two vertices is
maximized. This is exactly the matching problem on the bipartite graph
$G^{\prime}=(R\cup B,E^{\prime})$, with $R$ and $B$ being the red and blue
vertices, respectively, and $E^{\prime}=\\{\\{u,v\\}\in E\mid u\in R\wedge
v\in B\\}$. After computing an optimum matching, each edge of the matching
defines a cluster and unmatched vertices are packed into fair clusters
arbitrarily.

For the other direction, if we are given an instance $G^{\prime}=(R\cup
B,E^{\prime})$ for bipartite matching, we color all the vertices in $R$ red
and the vertices in $B$ blue. Then, a minimum-cost fair clustering is a
partition that maximizes the number of edges in each cluster as argued above.
As each vertex is part of exactly one cluster and all clusters consist of one
vertex in $R$ and one vertex in $B$, this corresponds to a maximum bipartite
matching in $G^{\prime}$.

By 4.3, the condition of Theorem 6.1 is met by all bipartite graphs. The
recent maxflow breakthrough [18] also gives an $m^{1+o(1)}$-time algorithm to
compute bipartite matchings, this then transfers also to Fair Correlation
Clustering with color ratio $1:1$. For Fair Correlation Clustering on forests,
we can do better as the reduction in Theorem 6.1 again results in a forest,
for which bipartite matching can be solved in linear time by standard
techniques. We present the algorithm here for completeness.

######  Theorem 6.3.

_Fair Correlation Clustering_ on forests with a color ratio $1:1$ can be
solved in time $\mathcal{O}(n)$.

######  Proof 6.4.

We apply Theorem 6.1 to receive a sub-forest of the input for which we have to
compute a maximum matching. We do so independently for each of the trees by
running the following dynamic program. We visit all vertices, but each one
only after we have already visited all its children (for example by employing
topological sorting). For each vertex $v$, we compute the maximum matching
$M_{v}$ in the subtree rooted at $v$ as well as the maximum matching
$M_{v}^{\prime}$ in the subtree rooted at $v$ assuming $v$ is not matched. We
directly get that $M_{v}^{\prime}$ is simply the union of the matchings
$M_{u}$ for each child $u$ of $v$. Further, either $M_{v}=M_{v}^{\prime}$ or
in $M_{v}$ there is an edge between $v$ and some child $u$. In the latter
case, $M_{v}$ is the union of $\\{u,v\\},M_{u}^{\prime},$ and the union of all
$M_{w}$ for all children $w\neq u$. Trying out all possible choices of $u$ and
comparing them among another and to $M_{v}^{\prime}$ yields $M_{v}$. In the
end, the maximum matching in the tree with root $r$ is $M_{r}$.

Each vertex is visited once. If the matchings are not naively merged during
the process but only their respective sizes are tracked and the maximum
matching is retrieved after the dynamic program by using a back-tracking
approach, the time complexity per vertex is linear in the number of its
children. Thus, the dynamic program runs in time in $\mathcal{O}(n)$.

Next, recall that Theorem 5.3 states that Fair Correlation Clustering on trees
with a diameter of at least 4 is NP-hard. With the next theorem, we show that
we can efficiently solve Fair Correlation Clustering on trees with a diameter
of at most 3, so our threshold of 4 is tight unless $\textsf{P}=\textsf{NP}$.

######  Theorem 6.5.

_Fair Correlation Clustering_ on trees with a diameter of at most 3 can be
solved in time $O(n)$.

######  Proof 6.6.

Diameters of 0 or 1 are trivial and the case of two colors in a ratio of $1:1$
is handled by Theorem 6.1. So, assume $d>2$ to be the minimum size of a fair
cluster. A diameter of two implies that the tree is a star. In a star, the
inter-cluster cost equals the number of vertices that are not placed in the
same cluster as the center vertex. By 2.2, every clustering of minimum cost
has minimum-sized clusters. As in a star, all these clusterings incur the same
inter-cluster cost of $n-d+1$ they all have the same Correlation Clustering
cost by 2.1. Hence, outputting any fair clustering with minimum-sized clusters
solves the problem. Such a clustering can be computed in time in
$\mathrm{O}(n)$.

If we have a tree of diameter 3, it consists of two adjacent vertices $u,v$
such that every vertex $w\in V\setminus\\{u,v\\}$ is connected to either $u$
or $v$ and no other vertex, see Figure 7.

Figure 7: Shape of every tree with diameter 3.

This is due to every graph of diameter 3 having a path of four vertices. Let
the two in the middle be $u$ and $v$. The path has to be an induced path or
the graph would not be a tree. We can attach other vertices to $u$ and $v$
without changing the diameter but as soon as we attach a vertex elsewhere, the
diameter increases. Further, there are no edges between vertices in
$V\setminus\\{u,v\\}$ as the graph would not be circle-free.

For the clustering, there are now two possibilities, which we try out
separately. Either $u$ and $v$ are placed in the same cluster or not. In both
cases, 2.2 gives that all clusters are of minimal size $d$. If $u$ and $v$ are
in the same cluster, all clusterings of fair minimum sized clusters incur an
inter-cluster cost of $n-d+2$ as all but $d-2$ vertices have to be cut from
$u$ and $v$. In $\mathrm{O}(n)$, we greedily construct such a clustering
$\mathcal{P}_{1}$. If we place $u$ and $v$ in separate clusters, the minimum
inter-cluster is achieved by placing as many of their respective neighbors in
their respective clusters as possible. After that, all remaining vertices are
isolated and are used to make these two clusters fair and if required form
more fair clusters. Such a clustering $\mathcal{P}_{2}$ is also computed in
$\mathrm{O}(n)$. We then return the cheaper clustering. This is a fair
clustering of minimum cost as either $u$ and $v$ are placed in the same
cluster or not, and for both cases, $\mathcal{P}_{1}$ and $\mathcal{P}_{2}$
are of minimum cost, respectively.

###  6.2 Color Ratio 1 : 2

We now give algorithms for Fair Correlation Clustering on forests that do not
require a certain diameter or degree. As a first step to solve these less
restricted instances, we develop an algorithm to solve Fair Correlation
Clustering on forests with a color ratio of $1:2$.

W.l.o.g., the vertices are colored blue and red with twice as many red
vertices as blue ones. We call a connected component of size 1 a _$b$
-component_ or _$r$ -component_, depending on whether the contained vertex is
blue or red. Analogously, we apply the terms _$br$ -component,
$rr$-component_, and _$brr$ -component_ to components of size 2 and 3.

####  6.2.1 Linear Time Attempt

Because of 2.2, we know that in every minimum-cost fair clustering each
cluster contains exactly 1 blue and 2 red vertices. Our high-level idea is to
employ two phases.

In the first phase, we partition the vertices of the forest $F$ in a way such
that in every cluster there are at most 1 blue and 2 red vertices. We call
such a partition a _splitting_ of $F$. We like to employ a standard tree
dynamic program that bottom-up collects vertices to be in the same connected
component and cuts edges if otherwise there would be more than 1 blue or 2 red
vertices in the component. We have to be smart about which edges to cut, but
as only up to 3 vertices can be placed in the topmost component, we have only
a limited number of possibilities we have to track to find the splitting that
cuts the fewest edges.

After having found that splitting, we employ a second phase, which finds the
best way to assemble a fair clustering from the splitting by merging
components and cutting as few additional edges as possible. As, by 2.1, a fair
partition with the smallest inter-cluster cost has a minimum Correlation
Clustering cost, this would find a minimum-cost fair clustering.

Unfortunately, the approach does not work that easily. We find that the number
of cuts incurred by the second phase also depends on the number of $br$\- and
$r$-components.

######  Lemma 6.7.

Let $F=(V,E)$ be an $n$-vertex forest with colored vertices in blue and red in
a ratio of $1:2$. Suppose in each connected component (in the above sense)
there is at most 1 blue vertex and at most 2 red vertices. Let $\\#(br)$ and
$\\#(r)$ be the number of $br$\- and $r$-components, respectively. Then, after
cutting $\max(0,\frac{\\#(br)-\\#(r)}{2})$ edges, the remaining connected
components can be merged such that all clusters consist of exactly 1 blue and
2 red vertices. Such a set of edges can be found in time in $\mathrm{O}(n)$.
Further, when cutting less than $\max(0,\frac{\\#(br)-\\#(r)}{2})$ edges, such
merging is not possible.

######  Proof 6.8.

As long as possible, we arbitrarily merge $b$-components with $rr$-components
as well as $br$-components with $r$-components. For this, no edges have to be
cut. Then, we split the remaining $rr$-components and merge the resulting
$r$-components with one $br$-component each. This way, we incur
$\max(0,\frac{\\#(br)-\\#(r)}{2})$ more cuts and obtain a fair clustering as
now each cluster contains two red and one blue vertex. This procedure is done
in time in $\mathrm{O}(n)$.

Further, there is no cheaper way. For each $br$-component to be merged without
further cuts we require an $r$-component. There are $\\#(r)$ $r$-components
and each cut creates either at most two $r$-components or one $r$-component
while removing a $br$-component. Hence, $\max(0,\frac{\\#(br)-\\#(r)}{2})$
cuts are required.

For our approach to work, the first phase has to simultaneously minimize the
number of cuts as well as the difference between $br$\- and $r$-components.
This is, however, not easily possible. Consider the tree in Figure 8.

Figure 8: A tree for which the splitting with the minimum number of cuts
(right) has 3 more $br$-components and 1 less $r$-component than a splitting
with one more edge cut (left).

There, with one additional cut edge we have three $br$-components less and one
$r$-component more. Using a standard tree dynamic program, therefore, does not
suffice as when encountering the tree as a subtree of some larger forest or
tree, we would have to decide between optimizing for the number of cut edges
or the difference between $br$\- and $r$-components. There is no trivial
answer here as the choice depends on how many $br$\- and $r$-components are
obtained in the rest of the graph. For our approach to work, we hence have to
track both possibilities until we have seen the complete graph, setting us
back from achieving a linear running time.

####  6.2.2 The Join Subroutine

In the first phase, we might encounter situations that require us to track
multiple ways of splitting various subtrees. When we reach a parent vertex of
the roots of these subtrees, we join these various ways of splitting. For
this, we give a subroutine called Join. We first formalize the output by the
following lemma, then give an intuition on the variables, and lastly prove the
lemma by giving the algorithm.

######  Lemma 6.9.

Let $R_{1},R_{2},\ldots,R_{\ell_{1}}$ for $\ell_{1}\in\mathbb{N}_{>1}$ with
$R_{i}\in(\mathbb{N}\cup\\{\infty\\})^{\ell_{2}}$ for
$\ell_{2}\in\mathbb{N},i\in[\ell_{1}]$ and $f$ be a computable function
$f\colon[\ell_{2}]\times[\ell_{2}]\rightarrow 2^{[\ell_{2}]}$. For
$x\in[\ell_{2}]$, let

$\displaystyle A_{x}$
$\displaystyle=\\{M\in\left([\ell_{2}]\right)^{\ell_{1}}\mid
x\in\widehat{f}(M[1],M[2],\ldots,M[\ell_{2}])\\},$ whereby for all
$x_{1},x_{2},\ldots\in[\ell_{2}]$ $\displaystyle\widehat{f}(x_{1},x_{2})$
$\displaystyle=f(x_{1},x_{2})$ and for all $2\leqslant k\leqslant\ell_{2}$
$\displaystyle\widehat{f}(x_{1},x_{2},\ldots,x_{k})$
$\displaystyle=\bigcup_{x\in\widehat{f}(x_{1},x_{2},\ldots,x_{k-1})}f(x,x_{k}).$

Then, an array $R\in(\mathbb{N}\cup\\{\infty\\})^{\ell_{2}}$ such that
$R[x]=\min_{M\in A_{x}}\sum_{i=1}^{\ell_{1}}R_{i}[M[i]]$ for all
$x\in[\ell_{2}]$ can be computed in time in
$\mathrm{O}(\ell_{1}\cdot\ell_{2}^{2}\cdot T_{f})$, where $T_{f}$ is the time
required to compute $f$.

As we later reuse the routine, it is formulated more generally than required
for this section. Here, for the $1:2$ case, assume we want to join the
splittings of the children $u_{1},u_{2},\ldots,u_{\ell_{1}}$ of some vertex
$v$. For example, assume $v$ has three children as depicted in Figure 9.

Figure 9: Exemplary graph for a Join subroutine.

Then, for each child $u_{i}$, let there be an array $R_{i}$ such that
$R_{i}[x]$ is the minimum number of cuts required to obtain a splitting of the
subtree $T_{u_{i}}$ that has exactly $x$ more $br$-components than
$r$-components. For our example, assume all edges between $v$ and its children
have to be cut. We see, that $R_{1}[-1]=1$ and $R_{1}[x]=\infty$ for
$x\neq-1$, as the only possible splitting for the subtree of $u_{1}$ cuts only
the edge to $v$ and has one more $r$-component than $br$-components. Further,
we have $R_{2}[1]=1$ (by only cutting $\\{v,u_{2}\\}$), $R_{2}[-1]=2$ (by
cutting both edges of $u_{2}$), and $R_{2}[x]=\infty$ for $x\notin\\{-1,1\\}$.
Last, note that $R_{3}=R_{2}$.

The function $f$ returns the set of indices that should be updated when
merging two possibilities. When a splitting of one child’s subtree has $x_{1}$
more $br$-components and a splitting of another child’s subtree has $x_{2}$
more $br$-components, then the combination of these splittings has
$x_{1}+x_{2}$ more $br$-components than $r$-components. Hence, the only index
to update is $f(x_{1},x_{2})=\\{x_{1}+x_{2}\\}$. Later, we will require to
update more than a single index, so $f$ is defined to return a set instead of
a single index. Note that by the definition of $f$ and $\widehat{f}$, each
value placed in $R[x]$ by the routine corresponds to choosing exactly one
splitting from each array $R_{i}$ such that the total difference between
$br$-components and $r$-components sums up to exactly $x$.

In our example, assume any splitting is chosen for each of the three subtrees.
Let $x_{i}$ denote the difference of $br$\- and $r$-components of the chosen
splitting for the subtree rooted at $u_{i}$ for $1\leqslant i\leqslant 3$.
Then, Join sets $R[x]$ for $x=x_{1}+x_{2}+x_{3}$. If there are multiple ways
to achieve an index $x$, the one with the minimum number of cuts is stored in
$R[x]$. In the example, we have 4 possibilities, as $x_{1}=-1$ and
$x_{2},x_{3}\in\\{-1,1\\}$. Note that $x_{1}=-1,x_{2}=-1,x_{3}=1$ and
$x_{1}=-1,x_{2}=1,x_{3}=-1$ both evaluate to $x=-1$. Hence, only one of the
two combinations is stored (the one with fewer cuts, here an arbitrary one as
both variants imply 4 cuts). For the resulting array $R$, we have
$R[-3]=5,R[-1]=4,R[1]=3$, and $R[x]=\infty$ for $x\notin\\{-3,-1,1\\}$.
Observe that the numbers of cuts in $R$ correspond to the sums of the numbers
of cuts in the subtrees for the respective choice of $x_{i}$.

We now describe how the Join subroutine is computed.

######  Proof 6.10 (Proof of 6.9).

The algorithm works in an iterative manner. Assume it has found the minimum
value for all indices using the first $i-1$ arrays and they are stored in
$R^{i-1}$. It then _joins_ the $i$-th array by trying every index $x_{1}$ in
$R^{i-1}$ with every index $x_{2}$ in $R_{i}$. Each time, for all indices
$x\in f(x_{1},x_{2})$, it sets $R^{i}[x]$ to $R^{i-1}[x_{1}]+R_{i}[x_{2}]$ if
it is smaller than the current element there. Thereby, it tries all possible
ways of combining the interim solution with $R_{i}$ and for each index tracks
the minimum that can be achieved. Formally, we give the algorithm in algorithm
1.

Input: $R_{1},R_{2},\ldots,R_{\ell_{1}}$ for $\ell_{1}\geqslant 2$ with
$R_{i}\in(\mathbb{N}\cup\\{\infty\\})^{\ell_{2}}$ for $0\leqslant i<\ell_{1}$,
and a computable function $f\colon[\ell_{2}]\times[\ell_{2}]\rightarrow
2^{[\ell_{2}]}$.

Output: $R\in(\mathbb{N}\cup\\{\infty\\})^{\ell_{2}}$ such that, for all
$x\in[\ell_{2}]$, $R[x]=\min_{M\in A_{x}}\sum_{i=1}^{\ell_{1}}R_{i}[M[i]]$
with $A_{x}=\\{M\in\left([\ell_{2}]\right)^{\ell_{1}}\mid
x\in\widehat{f}(M[1],M[2],\ldots,M[\ell_{2}])\\}$,
$\widehat{f}(x_{1},x_{2},\ldots,x_{k})=\bigcup_{x\in\widehat{f}(x_{1},x_{2},\ldots,x_{k-1})}f(x,x_{k})$,
and $\widehat{f}(x_{1},x_{2})=f(x_{1},x_{2})$.

1 $R\leftarrow R_{1}$

2 for  _$i\leftarrow 2$ to $\ell_{1}$_ do

3 $R^{\prime}\leftarrow R$

4 foreach  _$(x_{1},x_{2})\in\left([\ell_{2}]\right)^{2}$_ do

5 foreach  _$x\in f(x_{1},x_{2})$_ do

6
$R^{\prime}[x]\leftarrow\min\left(R^{\prime}[x],R[x_{1}]+R_{i}[x_{2}]\right)$

7

8 $R\leftarrow R^{\prime}$

Algorithm 1 The Join subroutine.

The algorithm terminates after $\mathrm{O}(k\cdot\ell^{2}\cdot T_{f})$
iterations due to the nested loops. We prove by induction that $R$ is a
solution of Join over the arrays $R_{1},\ldots,R_{i}$ after each iteration
$i$. The first one simply tries all allowed combinations of the arrays
$R_{1},R_{2}$ and tracks the minimum value for each index, matching our
definition of Join. Now assume the statement holds for some $i$. Observe that
we only update a value $R[x]$ if there is a respective $M\in A_{x}$, so none
of the values is too small. To show that no value is too large, take any
$x\in[\ell_{2}]$ and let $a$ be the actual minimum value that can be obtained
for $R[x]$ in this iteration. Let $j_{1},j_{2},\ldots,j_{i+1}$ with
$x\in\widehat{f}(j_{1},j_{2},\ldots,j_{i+1})$ be the indices that obtain $a$.
Then, there is $y\in[\ell_{2}]$ such that after joining the first $i$ arrays
the value at index $y$ is $a-R_{i+1}[j_{i+1}]$ and
$y\in\widehat{f}(j_{1},j_{2},\ldots,j_{i})$. This implies $R[y]\leqslant
a-R_{i+1}$ by our induction hypothesis. Further, as both
$x\in\widehat{f}(j_{1},j_{2},\ldots,j_{i+1})$ and
$y\in\widehat{f}(j_{1},j_{2},\ldots,j_{i})$, we have $x\in f(y,j_{i+1})$.
Thus, in this iteration, $R[x]$ is set to at most
$R[y]+R_{i+1}[j_{i+1}]\leqslant a$. With this, all values are set correctly.

Observe that in the case of $f(x_{1},x_{2})=\\{x_{1}+x_{2}\\}$, which is
relevant to this section, the loop in lines 4-6 computes the
$(\min,+)$-convolution of the arrays $R$ and $R_{i}$. Simply trying all
possible combinations as done in the algorithm has a quadratic running time.
This cannot be improved without breaking the MinConv Conjecture, which states
there is no algorithm computing the $(\min,+)$-convolution of two arrays of
length $n$ in time in $\mathrm{O}(n^{2-\varepsilon})$ for any constant
$\varepsilon>0$ [21].

####  6.2.3 The Tracking Algorithm

With the Join subroutine at hand, we are able to build a dynamic program
solving Fair Correlation Clustering on forests with two colors in a ratio of
$1:2$. We first describe how to apply the algorithm to trees and then
generalize it to work on forests.

In the first phase, for each possible difference between the number of
$br$-components and $r$-components, we compute the minimum number of cuts to
obtain a splitting with that difference. In the second phase, we find the
splitting for which the sum of edges cut in the first phase and the number of
edges required to turn this splitting into a fair partition is minimal. This
sum is the inter-cluster cost of that partition, so by 2.1 this finds a fair
partition with the smallest Correlation Clustering cost.

##### Splitting the tree.

In the first phase, our aim is to compute an array $D$, such that, for all
integers $-n\leqslant x\leqslant\frac{n}{3}$, $D[x]\subseteq E$ is a minimum-
sized set of edges such that $x=br(T-D[x])-r(T-D[x])$, where $br(T-D[x])$ and
$r(T-D[x])$ are the number of $br$\- and $r$-components in $T-D[x]$,
respectively. To mark the case if no such set exists, we expect
$D[x]=\mathbb{N}$ to have an infinitely large entry. We fill the array in a
dynamic programming way, by computing an array $D_{v}^{h}$ for each vertex
$v$, and every possible _head_ $h\in\\{\emptyset,r,b,rr,br\\}$. Here,
$D_{v}^{h}[x]$, is a minimum-sized set of edges such that in the subtree
$T_{v}$ rooted at $v$ upon removal we have exactly $x$ more $br$-components
than $r$-components. The head $h$ refers to the colors in the topmost
component, which is of particular interest as it might later contain vertices
from outside $T_{v}$ as well. Head $h=r$ refers to a component with a red
vertex, $h=br$ with a blue and a red vertex so on. This component is empty
($h=\emptyset$) if the edge above $v$ is cut. The head is not counted as an
$br$-component or $r$-component for the computation of $x$. Figure 10 gives
examples of how a head is composed from the splittings of the children.

(a)

(b)

(c)

(d)

(e)

Figure 10: Exemplary subtree with various possibilities to obtain a head.
Figures 10(a) and 10(b) show splittings with an $rr$-head (dark green). The
choice for the heads of the children (light green) is unambiguous as the only
way to obtain an $rr$-head is to choose the $r$-head for the left child and an
$\emptyset$-head for the right one. Both the left and the right variants have
to be considered as they differ in the number of $br$-components minus the
number of $r$-components. The splittings in Figures 10(c), 10(d) and 10(e)
create an $\emptyset$-head, as they cut the edge above the root of the
subtree, so no vertices of the subtree can be part of a component with
vertices outside the subtree. Out of these 3 splittings, however, only Figures
10(c) and 10(d) will be further considered as 10(e) obtains the same
difference between $br$\- and $r$-components as 10(c) but cuts one more edge.
We note that other splittings obtain an $\emptyset$-head as well that are not
listed here.

In the following, we only show how to compute
$\Delta_{v}^{h}[x]=|D_{v}^{h}[x]|$, the size of the set of edges to obtain a
respective splitting. The set $D_{v}^{h}[x]$ is, however, obtained by a simple
backtracking approach in the same asymptotic running time. If
$D_{v}^{h}[x]=\mathbb{N}$, we have $\Delta_{v}^{h}[x]=\infty$. We initialize
all values with $\Delta_{v}^{h}[x]=\infty$, meaning we know of no set of edges
which upon removal give that head and that difference between $br$\- and
$r$-components. Then, for every red leaf $v$ we set $\Delta_{v}^{r}[0]=0$ and
$\Delta_{v}^{\emptyset}[-1]=1$. For every blue leaf $v$ we set
$\Delta_{v}^{b}[0]=0$ and $\Delta_{v}^{\emptyset}[0]=1$. This concludes the
computations for the leaves, as the only possibilities are to cut the edge
above the leaf or not. Now suppose we have finished the computation for all
children $u_{1},u_{2},\ldots,u_{k}$ of some vertex $v$. Observe that at most
two children of $v$ are placed in a head with $v$. For every head
$h\in\\{\emptyset,r,b,rr,br\\}$ that is formable at vertex $v$, we try all
possibilities to obtain that head.

If $h\in\\{r,b\\}$ and $c(v)$ corresponds to $h$, this is done by choosing
$\emptyset$ heads for all children. There is no unique splitting of the
subtrees however, as for each subtree rooted at some child vertex $u_{i}$
there is a whole array $D_{u_{i}}^{\emptyset}$ of possible splittings with
different numbers of $br$\- and $r$-components. To find the best choices for
all child vertices, we employ the Join subroutine that, when called with
$f(x_{1},x_{2})=\\{x_{1}+x_{2}\\}$ and a list of arrays, returns an array $R$
such that, for all indices $x$ $R[x]$ is the minimum value obtained by summing
up exactly one value from each of the input arrays such that the indices of
the chosen values sum up to $i$. We hence set
$\Delta_{v}^{h}=\textsc{Join}(\Delta_{u_{1}}^{\emptyset},\ldots,\Delta_{u_{k}}^{\emptyset})$.
Here and in the following, we only call the Join subroutine with at least two
arrays. If we would only input a single array, we go on as if the Join
subroutine returned that array. We note that here our indexing ranges from
$-n$ to $\frac{n}{3}$ while the Join subroutine assumes positive indices. We
hence implicitly assume that an index of $x$ here maps to an index $x+n+1$ in
the subroutine.

If $h=br$ or both $h=rr$ and $c(v)$ corresponds to $r$, then the heads for all
children should be $\emptyset$ except for one child that we place in the same
component as $v$. It then has a head $h^{\prime}\in\\{r,b\\}$, depending on
$h$ and $c(v)$. We have $h^{\prime}=r$ if $h=rr$ and $c(v)$ corresponds to $R$
or $h=rb$ and $c(v)$ corresponds to $b$. Otherwise, $h^{\prime}=b$. For all
$i\in[k]$, we compute an array
$\Delta^{\prime}_{u_{i}}=\textsc{Join}(\Delta_{u_{1}}^{\emptyset},\ldots,\Delta_{u_{i-1}}^{\emptyset},\Delta_{u_{i}}^{h^{\prime}},\Delta_{u_{i+1}}^{\emptyset},\ldots,\Delta_{u_{k}}^{\emptyset})$,
referring to $u_{i}$ having the non-empty head. Lastly, for all $-n\leqslant
x\leqslant\frac{n}{3}$, we set
$\Delta_{v}^{h}[x]=\min_{i\in[k]}\Delta^{\prime}_{u_{i}}[x]$.

If $h=\emptyset$, then we have to try out all different possibilities for the
component $v$ is in and, in each case, cut the edge above $v$. First assume we
want to place $v$ in a $brr$-component. Then it has to be merged with to
vertices, either by taking a head $h^{\prime}\in\\{br,rr\\}$ at one child or
by taking heads $h_{1},h_{2}\in\\{r,b\\}$ at two children. The exact choices
for $h^{\prime},h_{1},h_{2}$ of course depend on $c(v)$. We compute an array
$\Delta_{h^{\prime}}=\textsc{Join}(\Delta_{u_{1}}^{\emptyset},\ldots,\Delta_{u_{i-1}}^{\emptyset},\Delta_{u_{i}}^{h^{\prime}},\Delta_{u_{i+1}}^{\emptyset},\ldots,\Delta_{u_{k}}^{\emptyset})$
for the first option. For the second option, we compute the arrays
$\Delta_{i,j}=\textsc{Join}(\Delta_{u_{1}}^{\emptyset},\ldots,\Delta_{u_{i-1}}^{\emptyset},\Delta_{u_{i}}^{h_{1}},\Delta_{u_{i+1}}^{\emptyset},\ldots,\Delta_{u_{j-1}}^{\emptyset},\Delta_{u_{j}}^{h_{2}},\Delta_{u_{j+1}}^{\emptyset},\ldots,\Delta_{u_{k}}^{\emptyset})$
for all pairs of children $u_{i},u_{j}$ of $v$ such that $i<j$ and
$\\{v,u_{i},u_{j}\\}$ is a $brr$-component. We now have stored the minimum
number of cuts for all ways to form a $brr$-component with $v$ and for all
possibilities for $x$ in the arrays $\Delta_{h^{\prime}}$ and $\Delta_{i,j}$
for all possibilities of $i,j$. However, $v$ may also be in an $r$-, $b$-,
$rr$-, or $br$-component. Hence, when computing $\Delta_{v}^{\emptyset}[x]$ we
take the minimum value at position $x$ not only among the arrays
$\Delta_{h^{\prime}}$ and $\Delta_{i,j}$ but also of the arrays
$\Delta_{v}^{r},\Delta_{v}^{br},\Delta_{v}^{rr}$, and $\Delta_{v}^{br}$. Note
that here we have to shift all values in $\Delta_{v}^{r}$ to the left by one
since by isolating $v$ we create another $r$-component. An entry we have
written into $\Delta_{v}^{r}[x]$ hence should actually be placed in
$\Delta_{v}^{r}[x-1]$. Similarly, we have to shift $\Delta_{v}^{br}$ to the
right, since here we create a new $br$-component at the top of the subtree.
Lastly, as long as $v$ is not the root of $T$, we have to increase all values
in $\Delta_{v}^{\emptyset}$ by one, reflecting the extra cut we have to make
above $v$.

After all computations are completed by the correctness of the Join subroutine
and an inductive argument, $\Delta_{v}^{h}$ is correctly computed for all
vertices $v$ and heads $h$. Note that in the Join subroutine, as
$f(x_{1},x_{2})$ returns the correct index for merging two subtrees,
$\widehat{f}(x_{1},x_{2},\ldots,x_{k})$ gives the correct index of merging $k$
subtrees. In particular, $\Delta_{r}^{\emptyset}$ is the array containing for
each $-n\leqslant x\leqslant\frac{n}{3}$ the minimum number of edges to cut
such that the there are exactly $x$ more $br$-components than $r$-components,
where $r$ is the root of $T$. By adjusting the Join subroutine to track the
exact combination that leads to the minimum value at each position, we also
obtain an array $D$ that contains not only the numbers of edges but the sets
of edges one has to cut or is marked with $\mathbb{N}$ if no such set exists.

At each node, computing the arrays takes time $\mathrm{O}(n^{5})$, which is
dominated by computing $\mathrm{O}(n^{2})$ arrays $D_{u,w}$ in time
$\mathrm{O}(n^{3})$ each by 6.9 since $\ell_{1},\ell_{2}\in\mathrm{O}(n)$.
This phase hence takes time in $\mathrm{O}(n^{6})$.

##### Assembling a fair clustering.

Let $D$ be the set computed in the first phase. Note that each set of edges
$D[x]$ directly gives a splitting, namely the partition induced by the
connected components in $T-D[x]$.

By 6.7, the cheapest way to turn the splitting given by $D[x]$ into a
clustering of sets of 1 blue and 2 red vertices is found in linear time and
incurs $\frac{\max(0,x)}{2}$ more cuts. Hence, we find the $-n\leqslant
x\leqslant\frac{n}{3}$ for which $|D[x]|+\max(0,\frac{x}{2})$ is minimal. We
return the corresponding clustering as it has the minimum inter-cluster cost.

This phase takes only constant time per splitting if we tracked the number of
components of each type in the first phase and is therefore dominated by the
first phase.

##### Forests.

Our algorithm is easily generalized to also solve Fair Correlation Clustering
on unconnected forests with two colors in a ratio of $1:2$ by slightly
adapting the first phase. We run the dynamic program as described above for
each individual tree. This still takes overall time in $\mathrm{O}(n^{6})$.
For each tree $T_{i}$ in the forest and every $h\in\\{\emptyset,r,b,rr,br\\}$,
let then $\Delta_{T_{i}}^{\emptyset}$ denote the array
$\Delta_{r}^{\emptyset}$ with $r$ being the root of tree $T_{i}$. To find a
splitting of the whole forest and not just on the individual trees, we perform
an additional run of the Join subroutine using these arrays $\Delta_{T_{i}}$
and the function $f(x_{1},x_{2})=\\{x_{1}+x_{2}\\}$. This gives us an array
$R$ such that $R[x]$ is the minimum number of cuts required to obtain a
splitting with exactly $x$ more $br$-components than $r$-components for the
whole tree rather than for the individual trees. Note that we choose the
$\emptyset$-head at each tree as the trees are not connected to each other, so
in order to find a splitting we do not yet have to consider how components of
different trees are merged, this is done in the second phase. The first phase
then outputs an array $D$ that contains the set of edges corresponding to $R$,
which is obtained by a backtracking approach. As the additional subroutine
call takes time in $\mathrm{O}(n^{3})$, the asymptotic run time of the
algorithm does not change. This gives the following result.

######  Theorem 6.11.

_Fair Correlation Clustering_ on forests with two colors in a ratio of $1:2$
can be solved in time in $\mathrm{O}(n^{6})$.

###  6.3 Small Clusters

To obtain an algorithm that handles more colors and different color ratios, we
generalize our approach for the $1:2$ color ratio case from the previous
section. We obtain the following.

######  Theorem 6.12.

Let $F$ be a forest of $n$ vertices, each colored in one of $k\geqslant 2$
colors. Let the colors be distributed in a ratio of $c_{1}:c_{2}:\ldots:c_{k}$
with $c_{i}\in\mathbb{N}_{>0}$ for all $i\in[k]$ and
$\gcd(c_{1},c_{2},\ldots,c_{k})=1$. Then _Fair Correlation Clustering_ on $F$
can be solved in time in $\mathrm{O}(n^{2\hskip
0.70004pt\mathrm{setvars}+\mathrm{setmax}+2}\cdot\mathrm{setvars}^{\mathrm{setmax}})$,
where $\mathrm{setvars}=\prod_{i=1}^{k}(c_{i}+1)$ and
$\mathrm{setmax}=\sum_{i=1}^{k}c_{i}$.

Once more, the algorithm runs in two phases. First, it creates a list of
possible splittings, i.e., partitions in which, for every color, every
component has at most as many vertices of that color as a minimum-sized fair
component has. In the second phase, it checks for these splittings whether
they can be merged into a fair clustering. Among these, it returns the one of
minimum cost. We first give the algorithm solving the problem on trees and
then generalize it to also capture forests.

##### Splitting the forest.

For the first phase in the 1:2 approach, we employed a dynamic program that
kept track of the minimum number to obtain a splitting for each possible cost
incurred by the reassembling in the second phase. Unfortunately, if we are
given a graph with $k\geqslant 2$ colors in a ratio of
$c_{1}:c_{2}:\ldots:c_{k}$, then the number of cuts that are required in the
second phase is not always as easily bounded by the difference of the number
of two component types like $r$\- and $br$-components in the $1:2$ case.
However, we find that it suffices to track the minimum number of cuts required
to obtain any possible coloring of a splitting.

We first bound the number of possible colorings of a splitting. As during the
dynamic program we consider splittings of a subgraph of $G$ most of the time,
we also have to count all possible colorings of splittings of less than $n$
vertices.

######  Lemma 6.13.

Let $U$ be a set of $n$ elements, colored in $k\in\mathbb{N}_{>1}$ colors, and
let $d_{1},d_{2},\ldots,d_{k}\in\mathbb{N}$. Let $\mathcal{S}$ be the set of
all possible partitions of subsets of $U$ such that for every color $i$ there
are at most $d_{i}$ vertices of that color in each cluster. Let $\mathcal{C}$
be the set of all colorings of partitions in $\mathcal{S}$. Then,
$|\mathcal{C}|\leqslant(n+1)^{\mathrm{setvars}-1}$, where
$\mathrm{setvars}=\prod_{i=1}^{k}(d_{i}+1)$.

######  Proof 6.14.

The number of sets with different colorings is at most $\mathrm{setvars}$ as
there are $0$ to $d_{i}$ many vertices of color $i$ in each component. Thus, a
coloring of a partition $\mathcal{P}$ using only these sets is characterized
by an array of size $\mathrm{setvars}$ with values in $[n]\cup\\{0\\}$ as no
component occurs more than $n$ times. There are $(n+1)^{\mathrm{setvars}}$
ways to fill such an array. However, as the set colorings together have to
form a partition, the last entry is determined by the first
$\mathrm{setvars}-1$ entries, giving only $(n+1)^{\mathrm{setvars}-1}$
possibilities.

With this, we employ a dynamic program similar to the one presented in
subsection 6.2 but track the minimum cut cost for all colorings of splittings.
It is given by the following lemma.

######  Lemma 6.15.

Let $F=(V,E)$ be a forest with vertices in $k$ colors. Further, let
$d_{1},d_{2},\ldots,d_{k}\in\mathbb{N}$ and $\mathcal{S}$ be the set of all
possible partitions of $V$ such that there are at most $d_{i}$ vertices of
color $i$ in each cluster for $i\in[k]$. Let $\mathcal{C}$ be the set of all
colorings of partitions in $\mathcal{S}$. Then, in time in
$\mathrm{O}(n^{2\hskip
0.70004pt\mathrm{setvars}+\mathrm{setmax}+2}\cdot\mathrm{setvars}^{\mathrm{setmax}})$
with $\mathrm{setvars}=\prod_{i=1}^{k}(d_{i}+1)$ and
$\mathrm{setmax}=\sum_{i=1}^{k}d_{i}$, for all $C\in\mathcal{C}$, we find a
minimum-sized set $D_{C}\subseteq E$ such that the connected components in
$F-D_{C}$ form a partition of the vertices with coloring $C$ or certify that
there is no such set.

######  Proof 6.16.

We first describe how to solve the problem on a tree $T$ and then generalize
the approach to forests. We call a partition of the vertices such that for
every color $i$ there are at most $d_{i}$ vertices of that color in each
cluster a _splitting_.

We employ a dynamic program that computes the set $D_{C}$ for the colorings of
all possible splittings and all subtrees rooted at each vertex in $T$. We do
so iteratively, by starting to compute all possible splittings at the leaves
and augmenting them towards the root. Thereby, the connected component that is
connected to the parent of the current subtree’s root is of particular
importance as it is the only connected component that can be augmented by
vertices outside the subtree. We call this component the _head_. Note that the
head is empty if the edge between the root and its parent is cut. We do not
count the head in the coloring of the splitting and only give it explicitly.
Formally, for every $v\in V$, every possible coloring of a splitting $C$, and
every possible coloring $h$ of the head we compute $D_{v}^{h}[C]\subseteq E$,
the minimum-sized set of edges such that the connected components of
$T_{v}-D_{v}^{h}[C]$ form a splitting with coloring $C$ and head $h$. We set
$D_{v}^{h}[C]=\mathbb{N}$, an infinitely large set, if no such set exists.

Let all $D_{v}^{h}[C]$ be initialized with $\mathbb{N}$. Then, for every leaf
$v$ with parent $w$, we set $D_{v}^{h_{c(v)}}[C_{\emptyset}]=\emptyset$, where
$h_{c(v)}$ is the coloring of the component $\\{v\\}$ and $C_{\emptyset}$ the
coloring of the partition over the empty set. Also, we set
$D_{v}^{h_{\emptyset}}[C_{c(v)}]=\\{\\{v,w\\}\\}$, where the vertex $v$ is not
placed in the head as the edge to its parent is cut. As to cut or not to cut
the edge above are the only options for leaves, this part of the array is now
completed.

Next, suppose we have finished the computation for all children of some vertex
$v$. For every possible coloring $h$ of the head that is formable at vertex
$v$, we try all possibilities to obtain that coloring.

To this end, first assume $h$ to be non-empty. Therefore, $v$ has to be placed
in the head. Let $h_{-c(v)}$ denote the coloring obtained by decreasing $h$ by
one at color $c(v)$. To obtain head $h$, we hence have to choose colorings of
splittings of the subtrees rooted at the children
$u_{1},u_{2},\ldots,u_{\ell}$ of $v$ such that their respective heads
$h_{u_{1}},h_{u_{2}},\ldots,h_{u_{\ell}}$ combine to $h_{-c(v)}$. A
_combination_ of colorings $C_{1},C_{2},\ldots,C_{\ell}$ refers to the
coloring of the union of partitions $M_{1},M_{2},\ldots,M_{\ell}$ that have
the respective colorings and is defined as the element-wise sum over the
arrays $C_{1},C_{2},\ldots,C_{\ell}$. Often, there are multiple ways to choose
heads for the child vertices that fulfill this requirement. As every head is
of size at most $\mathrm{setmax}$, $h_{-c(v)}$ and contains $v$, it is
composed of less than $\mathrm{setmax}$ non-empty heads. As there are at most
$\mathrm{setvars}$ possible heads and we have to choose less than
$\mathrm{setmax}$ children, there are at most
$\binom{n}{\mathrm{setmax}-1}\cdot\mathrm{setvars}^{\mathrm{setmax}-1}<n^{\mathrm{setmax}-1}\cdot\mathrm{setvars}^{\mathrm{setmax}-1}$
possible ways to form $h_{-c(v)}$ with the children of $v$. Let each way be
described by a function $H$ assigning each child of $v$ a certain, possibly
empty, head. Then, even for a fixed $H$, there are multiple splittings
possible. This stems from the fact that even if the head $H(u)$ for a child
$u$ is fixed, there might be multiple splittings of the subtree of $u$ with
different colorings resulting in that head. For each possible $H$, we hence
employ the Join subroutine with the arrays $D_{u}^{H(u)}$ for all children $u$
using the cardinality of the sets as input for the subroutine. For the sake of
readability, we index the arrays here by some vector $C$ instead of a single
numerical index as used in the algorithmic description of the Join subroutine.
We implicitly assume that each possible coloring is represented by a positive
integer. By letting these indices enumerate the vectors in a structured way,
converting between the two formats only costs an additional time factor in
$\mathrm{O}(n)$.

For $f(x_{1},x_{2})$ we give the function returning a set containing only the