# Completely greedy coin sets

Andrew J. Young

###### Abstract

We show that the binary coin set minimizes the number of coins needed to
guarantee the ability to make change in any one transaction and its asymptotic
uniform average cost is no worse than that of any completely greedy coin set.

##  1 Introduction

For our purposes, a _coin set_ is a set of positive integers containing $1$,
and a _sub-coin set_ is a subset of a coin set that is also a coin set, i.e.
it contains $1$. When enumerated, a coin set is always written in increasing
order and its $k$th element is a reference to this order. Let $\mathcal{C}$ be
a coin set. An element $c\in\mathcal{C}$ is a _coin_. One is said to _make
change_ at a positive integer $n$ by choosing a _representation_ in
$\mathcal{C}$, collection of coins $c\in\mathcal{C}$ that sum to $n$, i.e.
$n=\sum_{c\in\mathcal{C}}\alpha_{c}c$ for some $\alpha_{c}\in\mathbb{N}$. A
representation is _minimal_ if it uses the least possible number of coins,
$\sum_{c\in\mathcal{C}}\alpha_{c}$ is minimized. We say a coin set is _greedy_
if successively choosing the greatest lower bounding coin provides a minimal
representation for every positive integer $n$. A coin set $\mathcal{C}$ is
said to be _totally greedy_ [1] if the first $k$ elements of $\mathcal{C}$ are
greedy for all $1\leq k\leq\lvert\mathcal{C}\rvert$. A _transaction_ is a
positive integer of interest.

One problem is that of _optimal denomination_ , the coin set minimizing the
average coins per transaction. Under the greedy and totally greedy settings
the following pathological issue arises. Suppose one is interested in making
change for transactions in $\\{1,2,\ldots,N\\}$, for some $N$, then without
any further restrictions the optimal denomination is $\\{1,2,\ldots,N\\}$. To
combat this pathology we introduce completely greedy coin sets.

A coin set is said to be _completely greedy_ if all of its sub-coin sets are
greedy. With this restriction the maximum number of coins in a coin set is at
most logarithmic in $N$, see Lemma 5 and its succeeding remarks. Completely
greedy coin sets are characterized by specific subsets of cardinality $3$
(Proposition 4), and greediness of subsets of cardinality $3$ can be quickly
verified (Corollary 3). Moreover, the binary coin set, i.e.
$\\{1,2,\ldots,2^{k},\ldots\\}$, is completely greedy, completely unique
(Proposition 6), minimizes coin purse size (Proposition 1), and is
asymptotically optimal in some sense (Theorem 7).

While complete greediness is a rather strong condition, we believe it is
justified by its resilience to the loss of elements of a coin set different
from $1$. More specifically, suppose a store makes change using some coin set
$\mathcal{C}$. For practical purposes, as making change is in general
$NP$-hard [2], a greedy coin set is desirable. However, without complete
greediness, this property may be lost if the store were to run out of some
non-unit denominations.

##  2 Minimal coin purse

We begin by studying the minimum number of coins needed to guarantee the
ability to make change in any one transaction. To that end, given a coin set
$\mathcal{C}$, an _optimal coin purse for $\mathcal{C}$_ is the smallest list
of elements of $\mathcal{C}$ such that any one transaction can be represented
using elements of that list. Further minimizing over all possible coin sets
provides a _minimal coin purse_. Let $f_{N}(\mathcal{C})$ denote the size of
an optimal coin purse for a coin set $\mathcal{C}$ used in making change for
transactions in $\\{1,2,\ldots,N\\}$, and

$f_{N}^{\ast}:=\min_{\mathcal{C}}f_{N}(\mathcal{C})$

the size of a corresponding minimal coin purse.

######  Proposition 1.

$f_{N}^{\ast}=\lceil\log_{2}(N+1)\rceil$.

###### Proof.

Let $\mathcal{C}$ be a coin set. For a list $\ell=(\ell_{k})_{1\leq k\leq n}$
with $\ell_{k}\in\mathcal{C}$, let

$\mathcal{S}(\ell)=\left\\{\sum_{k=1}^{n}\beta_{k}\ell_{k}:\beta_{k}\in\\{0,1\\},\,\exists\beta_{k}\neq
0\right\\}.$

Then $\lvert\mathcal{S}(\ell)\rvert\leq 2^{n}-1$. Moreover, $f_{N}^{\ast}$ is
the length of a minimal list $\ell$ such that
$\mathcal{S}(\ell)\supset\\{1,\ldots,N\\}$. Thus
$f_{N}^{\ast}\geq\lceil\log_{2}(N+1)\rceil$ and the binary coin set
$\mathcal{C}_{0}=\\{1,2,\ldots,2^{\lceil\log_{2}(N+1)\rceil-1}\\}$ achieves
this bound. ∎

For $N=99$ this is $f_{99}^{\ast}=7$ achieved by $\\{1,2,4,8,16,32,64\\}$
using $3.19$ coins on average. The optimal, unrestricted, coin set of
cardinality $7$ uses $2.68$ coins on average [2].

##  3 Complete greediness

Let $\mathcal{C}$ be a coin set. In addition to greediness we shall consider
uniqueness. $\mathcal{C}$ is said to be _unique_ if every positive integer has
only one minimal representation, e.g., $\\{1,2,3\\}$ is not unique
$4=2+2=3+1$, for $\lvert\mathcal{C}\rvert\leq 3$ see [3]. Total and complete
uniqueness of coin sets are defined in the same manor as for greediness.
$\text{opt}(\cdot\,;\,\mathcal{C})$ and $\text{grd}(\cdot\,;\,\mathcal{C})$
denote the _optimal and greedy cost functions_ , i.e. number of elements in an
optimal and the greedy representations under $\mathcal{C}$.

A few remarks about greediness of coin sets. Greediness does not imply total
greediness [1], $\\{1,2,4,5,8\\}$ is greedy but $\\{1,2,4,5\\}$ is not, does
not imply complete greediness, $\\{1,3,5,7\\}$ is totally greedy but
$\\{1,5,7\\}$ is not greedy. All cardinality $2$ coin sets are greedy and if
$\mathcal{C}=\\{c_{1},\ldots,c_{n}\\}$ is not greedy the least violator is in
$(c_{3}+1,c_{n-1}+c_{n})$ [4].

######  Theorem 2.

[5, 1] Let $\mathcal{C}=\\{c_{1},\ldots,c_{n}\\}$ be a greedy coin set,
$c_{n+1}>c_{n}$ and $m=\lceil\frac{c_{n+1}}{c_{n}}\rceil$. Then
$\mathcal{C}^{\prime}=\mathcal{C}\cup\\{c_{n+1}\\}$ is greedy if and only if
$\mathrm{opt}(mc_{n}\,;\,\mathcal{C}^{\prime})=\mathrm{grd}(mc_{n}\,;\,\mathcal{C}^{\prime})$
if and only if $\mathrm{grd}(mc_{n}\,;\,\mathcal{C}^{\prime})\leq m$.

######  Corollary 3.

[4, 1] A coin set $\mathcal{C}=\\{1,a,b\\}$ is greedy if and only if
$b\geq\lceil\frac{b}{a}\rceil(a-1)+1$.

######  Proposition 4.

Let $\mathcal{C}=\\{c_{1},\ldots,c_{n}\\}$ be a coin set. The following are
equivalent.

  1. (i)

$\mathcal{C}$ is completely greedy;

  2. (ii)

All sub-coin sets of cardinality $3$ are greedy;

  3. (iii)

For all $k\geq 3$, $\\{c_{1},c_{k-1},c_{k}\\}$ is greedy.

###### Proof.

If $\lvert\mathcal{C}\rvert=1$ or $2$, then $\mathcal{C}$ is completely greedy
and $(ii)$, $(iii)$ are vacuously true. Suppose $\lvert\mathcal{C}\rvert\geq
3$. We begin with a technical result. For $a,b\geq 0$, $\lceil
ab\rceil\leq\lceil a\rceil\lceil b\rceil$. $(iii)\Longrightarrow(ii)$ Let
$\\{1,c_{i},c_{j}\\}$ be a sub-coin set. Then by assumption, for all $i<k\leq
j$, $\\{1,c_{k-1},c_{k}\\}$ is greedy and by Corollary 3
$c_{k}\geq\lceil\frac{c_{k}}{c_{k-1}}\rceil(c_{k-1}-1)+1$. Thus

$c_{j}\geq\left\lceil\frac{c_{j}}{c_{j-1}}\right\rceil(c_{j-1}-1)+1\geq\left(\prod_{k=i+1}^{j}\left\lceil\frac{c_{k}}{c_{k-1}}\right\rceil\right)(c_{i}-1)+1\geq\left\lceil\frac{c_{j}}{c_{i}}\right\rceil(c_{i}-1)+1,$

where the last inequality is the beginning result. Hence $\\{1,c_{i},c_{j}\\}$
is greedy by Corollary 3. $(ii)\Longrightarrow(i)$ Let
$\mathcal{C}_{k}=\\{c_{1},\ldots,c_{k}\\}$. $\mathcal{C}_{1}$ is completely
greedy. Suppose $\mathcal{C}_{k-1}$ is. Let $\mathcal{S}$ be a sub-coin set of
$\mathcal{C}_{k}$ containing $c_{k}$, otherwise $\mathcal{S}$ is greedy by the
inductive statement. Thus $\mathcal{S}\backslash\\{c_{k}\\}$ is greedy. Let
$c^{\ast}=\max\\{c:c\in\mathcal{S}\backslash\\{c_{k}\\}\\}$ and
$m=\lceil\frac{c_{k}}{c^{\ast}}\rceil$. Then
$\text{grd}(mc^{\ast}\,;\,\mathcal{S})\leq\text{grd}(mc^{\ast}\,;\\{1,c_{k}\\})=1+mc^{\ast}-c_{k}\leq
m$ by greediness of $\\{1,c^{\ast},c_{k}\\}$ and Corollary 3. Hence
$\mathcal{S}$ is greedy by Theorem 2. ∎

######  Lemma 5.

Let $\mathcal{C}=\\{c_{1},\ldots,c_{n}\\}$ be a coin set. If $\mathcal{C}$ is
completely greedy and totally unique, then, for all $1\leq k\leq n$ and $0\leq
i\leq k-1$, $c_{k}\geq 2^{i}c_{k-i}$.

###### Proof.

Obvious for $c_{1}=1$ and $c_{2}\geq 2$. For all $k\geq 3$, by complete
greediness, $\\{1,c_{k-1},c_{k}\\}$ is greedy. Thus $c_{k}\geq 2c_{k-1}-1$ by
Corollary 3, but $\\{1,\ldots,c_{k-1},2c_{k-1}-1\\}$ is not unique at
$2c_{k-1}$. Hence $c_{k}\geq 2c_{k-1}$. The rest follows by induction. ∎

For a coin set $\mathcal{C}=\\{c_{1},\ldots,c_{m}\\}$, let

$n(N):=\max\\{n:c_{n}\leq N\\}.$

If $\mathcal{C}$ is completely greedy and totally unique then $c_{n}\geq
2^{n-1}$ and $n(N)\leq\lceil\log_{2}(N+1)\rceil$. If the uniqueness is dropped
$c_{n}\geq 2^{n-2}+1$, for $n\geq 2$, and
$n(N)\leq\lfloor\log_{2}(N-1)\rfloor+2$, for $N\geq 2$.

######  Proposition 6.

Let $\mathcal{C}=\\{c_{1},\ldots,c_{n}\\}$ be a coin set. If $c_{k}|c_{k+1}$,
for all $1\leq k\leq n-1$, then $\mathcal{C}$ is completely greedy and
completely unique.

###### Proof.

By Proposition 4 and Corollary 3, $\mathcal{C}$ is completely greedy. It
suffices to show that $\mathcal{C}$ is unique. Suppose not. Let $N$ be the
least violator and $c_{a}$ its greatest lower bounding coin. Then
$N=\sum_{k=1}^{b}\alpha_{k}c_{k}$ for some $b<a$, otherwise $N-c_{a}$ would be
a lesser violator. As the representation is minimal and $c_{k}\lvert c_{k+1}$,
for all $1\leq k\leq b$, $\alpha_{k}c_{k}<c_{k+1}$ implies
$(\alpha_{k}+1)c_{k}\leq c_{k+1}$ and $\sum_{i=1}^{k}\alpha_{i}c_{i}<c_{k+1}$.
Hence $\sum_{k=1}^{b}\alpha_{k}c_{k}<c_{b+1}\leq c_{a}\leq N$. ∎

The binary coin set is the only completely greedy totally unique coin set
using one coin of each denomination to make change. Let
$\mathcal{C}=\\{c_{1},\ldots,c_{n}\\}$ be a coin set. Then, for $N\geq c_{n}$,

$f_{N}(\mathcal{C})\geq\left\lfloor\frac{N}{c_{n}}\right\rfloor+\sum_{k=1}^{n-1}\left\lfloor\frac{c_{k+1}-1}{c_{k}}\right\rfloor.$
(1)

Make change at $\lfloor\frac{N}{c_{n}}\rfloor c_{n}$ or
$\lfloor\frac{c_{k+1}-1}{c_{k}}\rfloor c_{k}$. If $\mathcal{C}$ is greedy,
then this is tight. Thus for a greedy coin set $\lfloor\frac{N}{c_{n}}\rfloor$
copies of $c_{n}$ are needed and $\lfloor\frac{c_{k+1}-1}{c_{k}}\rfloor$ of
$c_{k}$. If $\mathcal{C}$ is completely greedy and totally unique $c_{k+1}\geq
2c_{k}$ by Lemma 5 and for any $k$ strictly exceeding this bound $c_{k}$ must
be used more than once.

##  4 Asymptotics

Let

$\text{cost}(N\,;\,\mathcal{C}):=\sum_{k=1}^{N}\text{opt}(k\,;\,\mathcal{C})=\sum_{k=1}^{N}\text{grd}(k\,;\,\mathcal{C}),$

where the last equality holds if $\mathcal{C}$ is greedy, and
$\text{cost}(0\,;\,\mathcal{C}):=0$. A coin set is said to be infinite if
$n(N)\rightarrow\infty$. An infinite coin set is said to be (completely)
greedy/unique if the first $n$ terms are (completely) greedy/unique for any
finite $n$. Let $\mathcal{B}:=\\{1,2,\ldots,2^{n},\ldots\\}$ denote the
infinite binary coin set. Then [6]

$\text{cost}(N\,;\,\mathcal{B})=\frac{1}{2}N\log_{2}N+NF\left(\log_{2}N\right),$

where $F$ is a continuous nonpositive nowhere differentiable function of
period $1$. Thus

$\lim_{N\rightarrow\infty}\frac{\text{cost}(N\,;\,\mathcal{B})}{n(N)N}=\frac{1}{2},$

where $n(N)=\lceil\log_{2}(N+1)\rceil$.

######  Theorem 7.

Let $\mathcal{C}$ be an infinite completely greedy coin set. Then

$\limsup_{N\rightarrow\infty}\frac{\mathrm{cost}(N\,;\,\mathcal{C})}{\left(\lfloor\log_{2}(N-1)\rfloor+2\right)N}\geq\frac{1}{2}.$

###### Proof.

Dropping to a subsequence

$\limsup_{N\rightarrow\infty}\frac{\mathrm{cost}(N\,;\,\mathcal{C})}{\left(\lfloor\log_{2}(N-1)\rfloor+2\right)N}\geq\limsup_{n\rightarrow\infty}\frac{\mathrm{cost}(c_{n+1}-1\,;\,\mathcal{C})}{\left(\lfloor\log_{2}\left(c_{n+1}-2\right)\rfloor+2\right)(c_{n+1}-1)}.$

By Lemma 9,
$\mathrm{cost}(c_{n+1}-1\,;\,\mathcal{C})\geq\frac{1}{2}c_{n+1}\log
c_{n+1}+o(nc_{n+1})$ and, for a completely greedy coin set,
$n=n(c_{n+1}-1)\leq\lfloor\log_{2}(c_{n+1}-2)\rfloor+2$. ∎

Let $\mathcal{C}=\\{c_{1},\ldots,c_{n}\\}$ be a greedy coin set, then, for
$q\in\mathbb{N}$ and $0\leq r<c_{n}$,

$\displaystyle\text{cost}(qc_{n}+r\,;\,\mathcal{C})$
$\displaystyle=\frac{q(q-1)}{2}c_{n}+q\cdot\text{cost}(c_{n}-1\,;\,\mathcal{C}\backslash\\{c_{n}\\})+q(r+1)$
$\displaystyle\quad+\text{cost}(r\,;\,\mathcal{C}\backslash\\{c_{n}\\}).$

In particular,

$\text{cost}(qc_{n}-1\,;\,\mathcal{C})=\frac{q(q-1)}{2}c_{n}+q\cdot\text{cost}(c_{n}-1\,;\,\mathcal{C}\backslash\\{c_{n}\\}),$

where by abusive of notation $\text{cost}(-1\,;\,\mathcal{C}):=0$, and thusly

$\displaystyle\text{cost}(qc_{n}+r-1\,;\,\mathcal{C})$
$\displaystyle=\frac{q(q-1)}{2}c_{n}+q\cdot\text{cost}(c_{n}-1\,;\,\mathcal{C}\backslash\\{c_{n}\\})+qr$
(2)
$\displaystyle\quad+\text{cost}(r-1\,;\,\mathcal{C}\backslash\\{c_{n}\\}),$

for all $0\leq r<c_{n}$.

######  Lemma 8.

Let $\mathcal{C}=\\{c_{1},\ldots,c_{n},\ldots\\}$ be an infinite completely
greedy coin set. Then

$\mathrm{grd}(N\,;\,\mathcal{C})=o(N).$

###### Proof.

For all $k$, $c_{k+1}\geq 2c_{k}-1$ by Corollary 3. Inductively this implies
$c_{k}\geq 2^{k-2}$ and $c_{k}\leq 2^{-n+k}N+1$, for all $1\leq k\leq n$,
where $n=n(N)$. By (1), as equality holds for a greedy coin set,

$\displaystyle\mathrm{grd}(N\,;\,\mathcal{C})$ $\displaystyle\leq
f_{N}(\mathcal{C})$
$\displaystyle=\left\lfloor\frac{N}{c_{n}}\right\rfloor+\sum_{k=1}^{n-1}\left\lfloor\frac{c_{k+1}-1}{c_{k}}\right\rfloor$
$\displaystyle\leq\left\lfloor\frac{N}{2^{n-2}}\right\rfloor+\sum_{k=1}^{n-1}\left\lfloor\frac{2^{-n+k+1}N}{2^{k-2}}\right\rfloor$
$\displaystyle\leq n2^{-n+3}N.$

∎

######  Lemma 9.

Let $\mathcal{C}=\\{c_{1},\ldots,c_{n},\ldots\\}$ be an infinite completely
greedy coin set, $c_{n+1}=q_{n}c_{n}+r_{n}$, where $q_{n}$ and $r_{n}$ are
chosen by the division algorithm, $a_{n}=\lceil\frac{c_{n+1}}{c_{n}}\rceil$
and $s_{n}=\sum_{k=1}^{n}(b_{k}-1)$, where $b_{1}=a_{1}=q_{1}$ and, for $n\geq
2$,

$b_{n}=\begin{cases}a_{n}&q_{n}\leq s_{n-1}\\\ q_{n}&\text{else}\end{cases}.$

Then

$\mathrm{cost}(c_{n+1}-1\,;\,\mathcal{C})\geq\frac{s_{n}}{2}c_{n+1}+o(nc_{n+1}).$

Moreover,

$s_{n}\geq\max\\{n,\log_{2}c_{n+1}-1\\}.$

###### Proof.

It suffices to show that

$\mathrm{cost}(c_{n+1}-1\,;\,\mathcal{C})\geq\frac{s_{n}}{2}c_{n+1}-t_{n}o(1),$

where $t_{n}$ is at most $O(nc_{n+1})$. Let $t_{1}=0$ and, for $n\geq 2$,

$t_{n}=\begin{cases}(q_{n}+1)t_{n-1}+q_{n}c_{n}&r_{n}>0\text{ and }q_{n}\leq
s_{n-1}\\\ q_{n}t_{n-1}&\text{else}\end{cases}.$

For the order condition eventually $s_{n-1}\leq\frac{c_{n}}{n}$, for the
details see Lemma 10. Let $n_{0}$ be such an $n$, then $t_{n_{0}}\leq
Mn_{0}c_{n_{0}+1}$ for some $M\geq 1$. Let $n>n_{0}$ and suppose $t_{n-1}\leq
M(n-1)c_{n}$. If $r_{n}>0$, then by Corollary 3, as $\\{1,c_{n},c_{n+1}\\}$ is
greedy,

$q_{n}c_{n}+r_{n}=c_{n+1}\geq(q_{n}+1)(c_{n}-1)+1\qquad\Longrightarrow\qquad
r_{n}\geq c_{n}-q_{n}.$

Thus

$q_{n}\leq s_{n-1}\leq\frac{c_{n}}{n}\qquad\Longrightarrow\qquad(n-1)c_{n}\leq
n(c_{n}-q_{n})\leq nr_{n}$

and

$\displaystyle t_{n}$ $\displaystyle=(q_{n}+1)t_{n-1}+q_{n}c_{n}$
$\displaystyle\leq(q_{n}+1)M(n-1)c_{n}+q_{n}c_{n}$ $\displaystyle\leq
Mn(q_{n}c_{n}+r_{n})$ $\displaystyle=Mnc_{n+1}.$

For $c_{2}$, $r_{1}=0$ thus

$\text{cost}(c_{2}-1\,;\,\mathcal{C})=\frac{q_{1}(q_{1}-1)}{2}=\frac{s_{1}}{2}c_{2}.$

Suppose for $n$. Let $\mathcal{C}_{n}=\\{c_{1},\ldots,c_{n}\\}$. Then by (2)

$\displaystyle\text{cost}(c_{n+1}-1\,;\,\mathcal{C})$
$\displaystyle\quad=\text{cost}(q_{n}c_{n}+r_{n}-1\,;\,\mathcal{C}_{n})$
$\displaystyle\quad=\frac{q_{n}(q_{n}-1)}{2}c_{n}+q_{n}\cdot\text{cost}(c_{n}-1\,;\,\mathcal{C}_{n-1})+q_{n}r_{n}+\text{cost}(r_{n}-1\,;\,\mathcal{C}_{n-1})$
$\displaystyle\quad\geq\frac{q_{n}(q_{n}-1)}{2}c_{n}+q_{n}\frac{s_{n-1}}{2}c_{n}-q_{n}t_{n-1}o(1)+q_{n}r_{n}+\text{cost}(r_{n}-1\,;\,\mathcal{C}_{n-1})$
$\displaystyle\quad=\frac{q_{n}-1}{2}c_{n+1}-\frac{q_{n}-1}{2}r_{n}+\frac{s_{n-1}}{2}c_{n+1}-\frac{s_{n-1}}{2}r_{n}-q_{n}t_{n-1}o(1)+q_{n}r_{n}$
$\displaystyle\qquad+\text{cost}(r_{n}-1\,;\,\mathcal{C}_{n-1})$
$\displaystyle\quad=\frac{s_{n}}{2}c_{n+1}-\frac{b_{n}-q_{n}}{2}c_{n+1}+\frac{q_{n}+1-s_{n-1}}{2}r_{n}+\text{cost}(r_{n}-1\,;\,\mathcal{C}_{n-1})$
(3) $\displaystyle\qquad-q_{n}t_{n-1}o(1).$

The desired bound holds for $r_{n}=0$. Suppose $r_{n}>0$. If $q_{n}\leq
s_{n-1}$, then $b_{n}-q_{n}=1$ and

$\displaystyle\text{cost}(c_{n+1}-1\,;\,\mathcal{C})$
$\displaystyle\quad\geq\frac{s_{n}}{2}c_{n+1}-\frac{1}{2}(q_{n}c_{n}+r_{n})+\frac{q_{n}+1-s_{n-1}}{2}r_{n}+\text{cost}(r_{n}\\!-\\!1\,;\,\mathcal{C}_{n-1})$
$\displaystyle\qquad-q_{n}t_{n-1}o(1)$
$\displaystyle\quad=\frac{s_{n}}{2}c_{n+1}-\frac{1}{2}q_{n}c_{n}+\frac{q_{n}-s_{n-1}}{2}r_{n}+\text{cost}(r_{n}\\!-\\!1\,;\,\mathcal{C}_{n-1})-q_{n}t_{n-1}o(1).$

Moreover, by Corollary 3 $r_{n}\geq c_{n}-\min\\{q_{n},c_{n}-1\\}$. Thus by
Lemma 8

$\displaystyle\text{cost}(r_{n}-1\,;\,\mathcal{C}_{n-1})$
$\displaystyle\geq\text{cost}(c_{n}-\min\\{q_{n},c_{n}-1\\}-1\,;\,\mathcal{C}_{n-1})$
$\displaystyle=\text{cost}(c_{n}-1\,;\,\mathcal{C}_{n-1})-\sum_{i=0}^{\min\\{q_{n},c_{n}-1\\}-1}\text{grd}(c_{n}-i-1\,;\mathcal{C}_{n-1})$
$\displaystyle=\text{cost}(c_{n}-1\,;\,\mathcal{C}_{n-1})-\sum_{i=0}^{\min\\{q_{n},c_{n}-1\\}-1}o(c_{n}-i-1)$
$\displaystyle\geq\frac{s_{n-1}}{2}c_{n}-t_{n-1}o(1)-q_{n}o(c_{n})$
$\displaystyle=\frac{s_{n-1}}{2}c_{n}-t_{n-1}o(1)-q_{n}c_{n}o(1)$
$\displaystyle=\frac{1}{2}q_{n}c_{n}+\frac{s_{n-1}-q_{n}}{2}c_{n}-(t_{n-1}+q_{n}c_{n})o(1)$
$\displaystyle\geq\frac{1}{2}q_{n}c_{n}+\frac{s_{n-1}-q_{n}}{2}r_{n}-(t_{n-1}+q_{n}c_{n})o(1).$

Combining gives the desired bound, where
$q_{n}t_{n-1}+t_{n-1}+q_{n}c_{n}=t_{n}$. If $q_{n}>s_{n-1}$, then
$b_{n}=q_{n}$ and all terms in (4) are nonnegative. For the lower bounds on
$s_{n}$. If $q_{n}=1$, then $q_{n}\leq c_{2}-1=q_{1}-1=s_{1}\leq s_{n-1}$.
Thus $b_{n}=a_{n}\geq 2$ and $s_{n}\geq n$. Similarly,
$s_{1}=q_{1}-1\geq\log_{2}q_{1}=\log_{2}c_{2}$, where $\log_{2}x\leq x-1$ for
$x\geq 2$. If $r_{n}=0$

$\log_{2}c_{n+1}=\log_{2}q_{n}+\log_{2}c_{n}\leq q_{n}-1+\log_{2}c_{n}.$

If $q_{n}\geq 3$

$\log_{2}c_{n+1}\leq\log_{2}(q_{n}+1)+\log_{2}c_{n}\leq
q_{n}-1+\log_{2}c_{n},$

where $\log_{2}x\leq x-2$ for $x\geq 4$. Suppose $q_{n}\leq 2$ and $r_{n}>0$.
By Corollary 3 $c_{n+1}=2c_{n}-1,3c_{n}-1,3c_{n}-2$. For all $n$,

$\log_{2}c_{n+1}\leq\log_{2}a_{n}+\log_{2}c_{n}\leq a_{n}-1+\log_{2}c_{n}.$

As $s_{n}\geq n$, the only case for which $b_{n}\neq a_{n}$ is
$c_{2}-1=s_{1}<q_{2}=2$ or $c_{2}=2$ and $c_{3}=5$. Hence $s_{n}<\log c_{n+1}$
at most once and by at most $1$. ∎

######  Lemma 10.

Let $\mathcal{C}=\\{c_{1},\ldots,c_{n},\ldots\\}$ be an infinite completely
greedy coin set, $a_{n}=\lceil\frac{c_{n+1}}{c_{n}}\rceil$ and
$u_{n}=\sum_{k=1}^{n}(a_{k}-1)$. There exists $n_{0}$ such that for all $n\geq
n_{0}$

$c_{n}\geq nu_{n-1}.$

###### Proof.

Let $n\geq 3$ and

$g_{n}(\underline{a})=\left(\prod_{k=2}^{n-1}a_{k}\right)(a_{1}-1)+1-n\sum_{k=1}^{n-1}(a_{k}-1).$

By Corollary 3 $c_{n}-nu_{n-1}\geq g_{n}(\underline{a})$, where $a_{1}=c_{2}$.
Then

$\frac{\partial}{\partial
a_{1}}g_{n}(\underline{a})=\left(\prod_{k=2}^{n-1}a_{k}\right)-n,$

and, for $i\neq 1$,

$\frac{\partial}{\partial a_{i}}g_{n}(\underline{a})=\left(\prod_{k=2,k\neq
i}^{n-1}a_{k}\right)(a_{1}-1)-n.$

Thus, for all $i$,

$\frac{\partial}{\partial a_{i}}g_{n}(\underline{a})\geq 2^{n-3}-n.$

Let $n_{1}$ be such that $2^{n-3}\geq n$ for all $n\geq n_{1}$. Then, for all
$n\geq n_{1}$, $g_{n}$ is nondecreasing in each coordinate and it suffices to
show that the bound holds for $a_{i}=2$. Choose $n_{2}$ such that
$2^{n-2}+1\geq n(n-1)$ for all $n\geq n_{2}$. Let
$n_{0}=\max\\{3,n_{1},n_{2}\\}$. For all $n\geq n_{0}$, $c_{n}\geq nu_{n-1}$.
∎

## References

  * [1] L. Cowen, R. Cowen, and A. Steinberg, “Totally greedy coin sets and greedy obstructions,” Electr. J. Comb., vol. 15, p. R90, 2008.
  * [2] J. Shallit, “What this country needs is an 18-cent piece,” Mathematical Intelligencer, vol. 25, pp. 20–23, 2003.
  * [3] L. Bryant, J. Hamblin, and L. Jones, “A variation on the money-changing problem,” The American Mathematical Monthly, vol. 119, no. 5, pp. 406–414, 2012.
  * [4] D. Kozen and S. Zaks, “Optimal bounds for the change-making problem,” Theoretical Computer Science, vol. 123, no. 2, pp. 377–388, 1994.
  * [5] M. J. Magazine, G. L. Nemhauser, and L. E. Trotter, “When the greedy solution solves a class of knapsack problems,” Operations Research, vol. 23, no. 2, pp. 207–217, 1975.
  * [6] H. Delange, “Sur la fonction sommatoire de la fonction ”somme des chiffres”,” Enseign Math, vol. 21, pp. 31–47, 1975.


index of the coloring obtained by combining the colorings indexed by $x_{1}$
and $x_{2}$, which is computable in time in $\mathrm{O}(n)$. Combining the
colorings means for each set coloring summing the occurrences in both
partition colorings. Thereby, $\widehat{f}(x_{1},x_{2},\ldots,x_{k})$ as
defined in the Join subroutine returns the index of the combination of the
colorings indexed by $x_{1},x_{2},\ldots,x_{k}$. Note that there are at most
$n$ arrays and each is of length less than $(n+1)^{\mathrm{setvars}-1}$ as
there are so many different colorings by 6.13. After executing the Join
subroutine, by 6.9, we obtain an array $D_{H}$ that contains the minimum cut
cost required for all possible colorings that can be achieved by splitting
according to $H$. By modifying the Join subroutine slightly to use a simple
backtracking approach, we also obtain the set $D\subseteq E$ that achieves
this cut cost. We conclude our computation of $D_{v}^{h}$ by element-wisely
taking the minimum-sized set over all computed arrays $D_{H}$ for the possible
assignments $H$.

If $h$ is the empty head, i.e., the edge above $v$ is cut, then $v$ is placed
in a component that is either of size $\mathrm{setmax}$ or has a coloring
corresponding to some head $h^{\prime}$. In the first case, we compute an
array $D_{\text{full}}$ in the same manner as described above by trying all
suitable assignments $H$ and employing the Join subroutine. In the second
case, we simply take the already filled array $D_{v}^{h^{\prime}}$. Note that
in both cases we have to increment all values in the array by one to reflect
cutting the edge above $v$, except if $v$ is the root vertex. Also, we have to
move the values in the arrays around, in order to reflect that the component
containing $v$ is no longer a head but with the edge above $v$ cut should also
be counted in the coloring of the splitting. Hence, the entry
$D_{\text{full}}[C]$ is actually stored at $D_{\text{full}}[C_{-\text{full}}]$
with $C_{-\text{full}}$ being the coloring $C$ minus the coloring of a
minimum-sized fair cluster. If no such entry
$D_{\text{full}}[C_{-\text{full}}]$ exists, we assume it to be $\infty$. The
same goes for accessing the arrays $D_{v}^{h^{\prime}}$ where we have to
subtract the coloring $h^{\prime}$ from the index. Taking the element-wise
minimum-sized element over the such modified arrays $D_{\text{full}}$ and
$D_{v}^{h^{\prime}}$ for all possibilities for $h^{\prime}$ yields
$D_{v}^{\emptyset}$.

By the correctness of the Join subroutine and as we try out all possibilities
to build the specified heads and colorings at every vertex, we thus know that
after completing the computation at the root $r$ of $T$, the array
$D_{r}^{\emptyset}$ contains for every possible coloring of a splitting of the
tree the minimum cut cost to achieve that coloring.

For each of the $n$ vertices and the $\mathrm{setvars}$ possible heads, we
call the Join subroutine at most
$n^{\mathrm{setmax}-1}\cdot\mathrm{setvars}^{\mathrm{setmax}-1}$ many times.
Each time, we call it with at most $n$ arrays and, as by 6.13 there are
$\mathrm{O}(n^{\mathrm{setmax}})$ possible colorings, all these arrays have
that many elements. Hence, each subroutine call takes time in
$\mathrm{O}(n\cdot\left(n^{\mathrm{setvars}}\right)^{2})=\mathrm{O}(n^{2\hskip
0.70004pt\mathrm{setvars}+1})$, so the algorithm takes time in
$\mathrm{O}(n^{2\hskip
0.70004pt\mathrm{setvars}+\mathrm{setmax}+2}\cdot\mathrm{setvars}^{\mathrm{setmax}})$,
including an additional factor in $\mathrm{O}(n)$ to account for converting
the indices for the Join subroutine.

When the input graph is not a tree but a forest $F$, we apply the dynamic
program on every tree in the forest. Then, we additionally run the Join
subroutine with the arrays for the $\emptyset$-head at the roots of all trees
in the forest. The resulting array contains all minimum-cost solutions from
all possible combinations from colorings of splittings from the individual
trees and is returned as output. The one additional subroutine does not change
the asymptotic running time.

Because of Lemmas 2.2 and 4.3 it suffices to consider partitions as possible
solutions that have at most $c_{i}$ vertices of color $i$ in each cluster, for
all $i\in[k]$. We hence apply 6.15 on the forest $F$ and set $d_{i}=c_{i}$ for
all $i\in[k]$. This way, for every possible coloring of a splitting we find
the minimum set of edges to obtain a splitting with that coloring.

##### Assembling a fair clustering.

Let $D$ be the array produced in the first phase, i.e., for every coloring $C$
of a splitting, $D[C]$ is a minimum-sized set of edges such that the connected
components in $F-D[C]$ induce a partition with coloring $C$. In the second
phase, we have to find the splitting that gives the minimum Correlation
Clustering cost. We do so by deciding for each splitting whether it is
_assemblable_ , i.e., whether its clusters can be merged such that it becomes
a fair solution with all clusters being no larger than $\mathrm{setmax}$.
Among these, we return the one with the minimum inter-cluster cost computed in
the first phase.

This suffices because of the following reasons. First, note that deciding
assemblability only depends on the coloring of the splitting so it does not
hurt that in the first phase we tracked only all possible colorings of
splittings and not all possible splittings themselves. Second, we do not have
to consider further edge cuts in this phase: Assume we have a splitting $S$
with coloring $C_{S}$ and we would obtain a better cost by further cutting $a$
edges in $S$, obtaining another splitting $S^{\prime}$ of coloring
$C_{S^{\prime}}$. However, as we filled the array $D$ correctly, there is an
entry $D[C_{S^{\prime}}]$ and $|D[C_{S^{\prime}}]|\leqslant|D[C_{S}]|+a$. As
we will consider this value in finding the minimum anyway, there is no need to
think about cutting the splittings any further. Third, the minimum inter-
cluster cost yields the minimum Correlation Clustering cost by 2.1. When
merging clusters, the inter-cluster cost computed in the first phase may
decrease but not increase. If it decreases, we overestimate the cost. However,
this case implies that there is an edge between the two clusters and as they
are still of size at most $\mathrm{setmax}$ when merged, in the first phase we
will also have found another splitting considering this case.

We employ a dynamic program to decide the assemblability for all possible
$\mathrm{O}(n^{\mathrm{setvars}})$ colorings of splittings. Define the _size_
of a partition coloring to be the number of set colorings in that partition
coloring (not necessarily the number of different set colorings). We decide
assemblability for all possible colorings of splittings from smallest to
largest. Note that each such coloring is of size at least
$\frac{n}{\mathrm{setmax}}$. If it is of size exactly
$\frac{n}{\mathrm{setmax}}$, then all contained set colorings are of size
$\mathrm{setmax}$, so this partition coloring is assemblable if and only if
all set colorings are fair. Now assume we have found all assemblable colorings
of splittings of size exactly $j\geqslant\frac{n}{\mathrm{setmax}}$. Assume a
partition coloring $C$ of size $j+1$ is assemblable. Then, at least two set
colorings $C_{1},C_{2}$ from $C$ are merged together. Hence, let $C^{\prime}$
be the partition coloring obtained by removing the set colorings $C_{1},C_{2}$
from $C$ and adding the set coloring of the combined coloring of $C_{1}$ and
$C_{2}$. Now, $C^{\prime}$ is of size $j$ and is assemblable. Thus, every
assemblable splitting with $j+1$ components has an assemblable splitting with
$j$ components. The other way round, if we split a set coloring of an
assemblable partition coloring of size $j$ we obtain an assemblable partition
coloring of size $j+1$. Hence, we find all assemblable colorings of splittings
of size $j+1$ by for each assemblable partition coloring of size $j$ (less
than $n^{\mathrm{setvars}}$ many) trying each possible way to split one of its
set colorings (less than $i\cdot 2^{\mathrm{setmax}}$ as there are $j$ set
colorings each of size at most $\mathrm{setmax}$). Thus, to compute all
assemblable colorings of splittings of size $j+1$, we need time in
$\mathrm{O}(n^{\mathrm{setvars}}\cdot j\cdot 2^{\mathrm{setmax}})$, which
implies a total time for the $n-\frac{n}{\mathrm{setmax}}$ iterations in the
second phase in $\mathrm{O}(n^{\mathrm{setvars}+2}\cdot 2^{\mathrm{setmax}})$.
This is dominated by the running time of the first phase. The complete
algorithm hence runs in time in
$\mathrm{O}(n^{2\mathrm{setvars}+\mathrm{setmax}+2}\cdot\mathrm{setvars}^{\mathrm{setmax}})$,
which implies Theorem 6.12.

This gives an algorithm that solves Fair Correlation Clustering on arbitrary
forests. The running time however may be exponential in the number of vertices
depending on the color ratio in the forest.

###  6.4 Few Clusters

The algorithm presented in the previous section runs in polynomial time if the
colors in the graph are distributed in a way such that each cluster in a
minimum-cost solution is of constant size. The worst running time is obtained
when there are very large but few clusters. For this case, we offer another
algorithm, which runs in polynomial time if the number of clusters is
constant. However, it is limited to instances where the forest is colored in
two colors in a ratio of $1:c$ for some $c\in\mathbb{N}$.

The algorithm uses a subroutine that computes the minimum number of cuts that
are required to slice off clusters of specific sizes from the tree. It is
given by 6.17.

######  Lemma 6.17.

Let $T=(V,E)$ be a tree rooted at $r\in V$ and $k\in\mathbb{N}$. Then, we can
compute an array $R$ such that, for each $a_{0}\in[n]$ and
$a={a_{1},a_{2},\ldots,a_{k}}\in\left([n-1]\cup\\{0\\}\right)^{k}$ with
$a_{i}\geqslant a_{i+1}$ for $i\in[k-1]$ and $\sum_{i=0}^{k}a_{i}=n$, we have
that $R[a_{0},a]$ is the partition
$\mathcal{P}=\\{S_{0},S_{1},\ldots,S_{k}\\}$ of $V$ with minimum inter-cluster
cost that satisfies $r\in S_{0}$ and $|S_{i}|=a_{i}$ for $i\in[k]$. The
computation time is in $\mathrm{O}((k+3)!\cdot n^{2k+3})$.

######  Proof 6.18.

We give a construction such that $R[a_{0},a]$ stores not the partition itself
but the incurred inter-cluster cost. By a simple backtracking approach, the
partitions are obtained as well.

We employ a dynamic program that involves using the Join subroutine. For the
sake of readability, we index the arrays here by some vector $a\in[n]^{k}$ and
$a_{0}\in[n]$ instead of a single numerical index as used in the algorithmic
description of the Join subroutine. We implicitly assume that each possible
$a_{0},a$ is represented by some index in $[n^{k+1}]$. 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}(k)$.

Starting at the leaves and continuing at the vertices for which all children
have finished their computation, we compute an array $R_{v}$ with the
properties described for $R$ but for the subtree $T_{v}$ for each vertex $v\in
V$. In particular, for every vertex $v$ we do the following. Let $R_{v}^{0}$
be an array with $\infty$-values at all indices except for
$R_{v}^{0}[1,(0,0,\ldots,0)]=0$, as this is the only possible entry for the
tree $T[\\{v\\}]$.

If $v$ has no children, then $R=R_{v}^{0}$. Otherwise, let the children of $v$
be $u_{1},u_{2},\ldots,u_{\ell}$. Then we call the Join subroutine with the
arrays $R_{v}^{0},R_{u_{1}},R_{u_{2}},\ldots,R_{u_{\ell}}$. We have to define
$f$ such that it gives all possibilities to combine the children’s subtrees
partitions and $v$. For all possible values of $a_{0},a$ and
$a_{0}^{\prime},a^{\prime}$ recall that
$f((a_{0},a),(a_{0}^{\prime},a^{\prime}))$ should return a set of indices of
the form $(a_{0}^{\prime\prime},a^{\prime\prime})$. Each such index describes
a combination of all possibilities for $v$ and the already considered children
($a_{0},a$) and the possibilities for the next child
($a_{0}^{\prime},a^{\prime}$). First, we consider the possibility to cut the
edge between $v$ and the child $u$ that is represented by
$(a_{0}^{\prime},a^{\prime\prime})$. Then, we add all possible ways of merging
the two sets with their $k+1$ clusters each. As we cut the edge $\\{u,v\\}$,
there are $k$ possible ways to place the cluster containing $u$ (all but the
cluster containing $v$) and then there are $k!$ ways to assign the remaining
clusters. All these are put into the set
$f((a_{0},a),(a_{0}^{\prime},a^{\prime}))$. Second, we assume the edge
$\\{u,v\\}$ is not cut. Then, the clusters containing $v$ and $u$ have to be
merged, so there are only $k!$ possible ways to assign the other clusters. In
particular, for all indices $(a_{0}^{\prime\prime},a^{\prime\prime})$ put into
$f((a_{0},a),(a_{0}^{\prime},a^{\prime}))$ this way, we have
$a_{0}^{\prime\prime}=a_{0}+a_{0}^{\prime}$. Note that $f$ can be computed in
$\mathrm{O}(k\cdot k!)$. Note that $\widehat{f}(x_{1},x_{2},\ldots,x_{\ell})$
as defined in the Join subroutine lists all possibilities to cut the combined
tree as it iteratively combines all possibilities for the first child and the
vertex $v$ and for the resulting tree lists all possible combinations with the
next child and so on. The Join subroutine takes time in
$\mathrm{O}((k+1)\cdot\left(n^{k+1}\right)^{2}\cdot(k\cdot k!)\cdot k)$, which
is in $\mathrm{O}((k+3)!\cdot n^{2k+2})$. All $\mathrm{O}(n)$ calls of the
subroutine hence take time in $\mathrm{O}((k+3)!\cdot n^{2k+3})$.

With this, we are able to give an algorithm for graphs with two colors in a
ratio of $1:c$, which runs in polynomial time if there is only a constant
number of clusters, i.e., if $c\in\Theta(n)$.

######  Theorem 6.19.

Let $F$ be an $n$-vertex forest with two colors in a ratio of $1:c$ with
$c\in\mathbb{N}_{>0}$ and let $p=\frac{n}{c+1}$. Then, _Fair Correlation
Clustering_ on $F$ can be solved in $\mathrm{O}(n^{p^{3}+p^{2}+p})$.

######  Proof 6.20.

Note that, if there are $c$ red vertices per 1 blue vertex, $p=\frac{n}{c+1}$
is the number of blue vertices. By 2.2, any minimum-cost clustering consists
of $p$ clusters, each containing exactly one blue vertex, and from 2.1 we know
that it suffices to minimize the number of edges cut by any such clustering.
All blue vertices are to be placed in separate clusters. They are separated by
cutting at most $p-1$ edges, so we try all of the
$\mathrm{O}((p-1)\cdot\binom{n-1}{p-1})$ subsets of edges of size at most
$p-1$. Having cut these edges, we have $\ell$ trees
$T_{1},T_{2},\ldots,T_{\ell}$, with $p$ of them containing exactly one blue
vertex and the others no blue vertices. We root the trees at the blue vertex
if they have one or at an arbitrary vertex otherwise. For each tree $T_{i}$,
let $r_{i}$ be the number of red vertices. If we have exactly $p$ trees and
$r_{i}=c$ for all $i\in[p]$, we have found a minimum-cost clustering, where
the $i$-th cluster is simply the set of vertices of $T_{i}$ for all $i\in[p]$.
Otherwise, we must cut off parts of the trees and assign them to other
clusters in order to make the partition fair. To this end, for each tree
$T_{i}$ we compute an array $R_{i}$ that states the cost of cutting up to
$p-1$ parts of certain sizes off. More precisely,
$R_{i}[(a_{1},a_{2},\ldots,a_{p-1})]$ is the number of cuts required to cut
off $p-1$ clusters of size $a_{1},a_{2},\ldots,a_{p-1}$, respectively, and
$\infty$ if there is no such way as $\sum_{i=1}^{p-1}>r_{i}$. It suffices to
compute $R_{i}[(a_{1},a_{2},\ldots,a_{p-1})]$ with $0\leqslant a_{i}\leqslant
a_{i+1}\leqslant n$ for $i\in[p-2]$.

We compute these arrays employing 6.17. Note that here we omitted the $a_{0}$
used in the lemma, which here refers to the number of vertices _not_ cut from
the tree. However, $a_{0}$ is still unambiguously defined over $a$ as all the
values sum up to the number of vertices in this tree. Further, by connecting
all trees without blue vertices to some newly added auxiliary vertex $z$ and
using this tree rooted at $z$ as input to 6.17, we reduce the number of
subroutine calls to $p+1$. Then, the only entries from the array obtained for
the all-red tree we consider are the ones with $a_{0}=1$ as we do not want to
merge $z$ in a cluster but every vertex except $z$ from this tree has to be
merged into another cluster. We call the array obtained from this tree $R_{0}$
and the arrays obtained for the other trees $R_{1},R_{2},\ldots,R_{p}$,
respectively.

Note that every fair clustering is characterized by choosing one entry from
each array $R_{i}$ and assigning the cut-off parts to other clusters. As each
array has less than $\frac{n^{p}}{p!}$ entries and there are at most
$(p!)^{p}$ ways to assign the cut-off parts to clusters, there are at most
$n^{p^{2}}$ possibilities in total. For each of these, we compute in linear
time whether they result in a fair clustering. Among these fair clusterings,
we return the one with the minimum inter-cluster cost, computed by taking the
sum over the chosen entries from the arrays $R_{i}$. By 2.1, this clustering
has the minimum Correlation Clustering cost. We obtain a total running time of

$\mathrm{O}((p-1)\cdot\binom{n-1}{p-1}\cdot\left((p+1)\cdot\left(n^{p+3}+n^{p^{2}+p-2}\right)+n^{p^{2}+1}\right))\subseteq\mathrm{O}(n^{p^{3}+p^{2}+p}).$

Combining the results of Theorems 6.12 and 6.19, we see that for the case of a
forest with two colors in a ratio of $1:c$ for some $c\in\mathbb{N}_{>0}$,
there are polynomial-time algorithms when the clusters are either of constant
size or have sizes in $\Theta(n)$. As Theorem 5.1 states that Fair Correlation
Clustering on forests is NP-hard, we hence know that this hardness evolves
somewhere between the two extremes.

##  7 Relaxed Fairness

It might look like the hardness results for Fair Correlation Clustering are
due to the very strict definition of fairness, which enforces clusters of a
specific size on forests. However, in this section, we prove that even when
relaxing the fairness requirements our results essentially still hold.

###  7.1 Definitions

We use the relaxed fairness constraint as proposed by Bera et al. [11] and
employed for Fair Correlation Clustering by Ahmadi et al. [1]. For the
following definitions, given a set $U$ colored by a function $c:U\rightarrow
k$, by $U_{i}=\\{u\in U\mid c(u)=i\\}$ we denote the set of vertices of color
$i$ for all $i\in[k]$.

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

Let $U$ be a finite set of elements colored by a function $c:U\rightarrow[k]$
for some $k\in\mathbb{N}_{>0}$ and 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]$.
Then, some $S\subseteq U$ is relaxed fair with regard to the $q_{i}$ and
$p_{i}$ if and only if for all colors $i\in[k]$ we have
$p_{i}\leqslant\frac{|S\cap U_{i}|}{|S|}\leqslant q_{i}$.

Note that we require $p_{i}$ and $q_{i}$ to be such that an exact fair
solution is also relaxed fair. Further, we exclude setting $p_{i}$ or $q_{i}$
to 0 as this would allow clusters that do not include every color, which we do
not consider fair.

######  Definition 7.2 (Relaxed 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}$ and 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]$.
Then, a partition $S_{1}\cup S_{2}\cup\ldots\cup S_{\ell}=U$ is relaxed fair
with regard to the $q_{i}$ and $p_{i}$ if and only if all sets
$S_{1},S_{2},\ldots,S_{\ell}$ are relaxed fair with regard to the $q_{i}$ and
$p_{i}$.

Relaxed Fair Correlation Clustering
Input: Graph $G=(V,E)$, coloring $c\colon V\rightarrow[k]$,
$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]$. Task: Find a relaxed fair partition $\mathcal{P}$
of $V$ with regard to the $p_{i}$ and $q_{i}$ that minimizes
$\text{cost}(\mathcal{P})$.

While we use the above definition for our hardness results, we restrict the
possibilities for the $p_{i}$ and $q_{i}$ for our algorithms.

######  Definition 7.3 ($\alpha$-relaxed Fair Set).

Let $U$ be a finite set of elements colored by a function $c:U\rightarrow[k]$
for some $k\in\mathbb{N}_{>0}$ and let $0<\alpha<1$. Then, some $S\subseteq U$
is $\alpha$-relaxed fair if and only if it is relaxed fair with regard to
$p_{i}=\frac{\alpha|U_{i}|}{|U|}$ and $q_{i}=\frac{|U_{i}|}{\alpha|U|}$ for
all $i\in[k]$.

######  Definition 7.4 ($\alpha$-relaxed 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}$ and let $0<\alpha<1$. Then, a partition
$S_{1}\cup S_{2}\cup\ldots\cup S_{\ell}=U$ is $\alpha$-relaxed fair if and
only if all sets $S_{1},S_{2},\ldots,S_{\ell}$ are $\alpha$-relaxed fair.

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

###  7.2 Hardness for Relaxed Fairness

The hardness result for exact fairness on paths, see Theorem 5.7, directly
carries over to the relaxed fairness setting. This is due to it only
considering instances in which there are exactly two vertices of each color.
As any relaxed fair clustering still requires at least one vertex of every
color in each cluster, this means that every relaxed clustering either
consists of a single cluster or two clusters, each with one vertex of every
color. Thereby, relaxing fairness makes no difference in these instances.

######  Corollary 7.5.

_Relaxed Fair Correlation Clustering_ on paths is _NP_ -hard, even when
limited to instances with exactly 2 vertices of each color.

Our other hardness proofs for relaxed fairness are based on the notion that we
can use similar constructions as for exact fairness and additionally prove
that in these instances the minimum-cost solution has to be exactly fair and
not just relaxed fair. To this end, we require a lemma giving a lower bound on
the intra-cluster cost of clusterings.

######  Lemma 7.6.

Let $G=(V,E)$ be an $n$-vertex $m$-edge graph and $\mathcal{P}$ a partition of
$V$ with an inter-cluster cost of $\chi$. Then, the intra-cluster cost of
$\mathcal{P}$ is at least $\frac{n^{2}}{2|\mathcal{P}|}-\frac{n}{2}-m+\chi$.
If $|S|=\frac{n}{|\mathcal{P}|}$ for all clusters $S\in\mathcal{P}$, then the
intra-cluster cost of $\mathcal{P}$ is exactly
$\psi=\frac{n^{2}}{2|\mathcal{P}|}-\frac{n}{2}-m+\chi$.

######  Proof 7.7.

We first prove the lower bound. We employ the Cauchy-Schwarz inequality,
stating that for every $\ell\in\mathbb{N}$, $x_{1},x_{2},\ldots,x_{\ell}$, and
$y_{1},y_{2},\ldots,y_{\ell}$, we have
$\left(\sum_{i=1}^{\ell}x_{i}y_{i}\right)^{2}\leqslant\left(\sum_{i=1}^{\ell}x_{i}^{2}\right)\cdot\left(\sum_{i=1}^{\ell}y_{i}^{2}\right)$.
In particular, it holds that
$\left(\sum_{i=1}^{\ell}x_{i}\right)^{2}\leqslant\ell\cdot\sum_{i=1}^{\ell}x_{i}^{2}$.
Observe that we can write the intra-cluster cost $\psi$ of $\mathcal{P}$ as

$\displaystyle\psi$
$\displaystyle=\left(\sum_{S\in\mathcal{P}}\frac{|S|\cdot(|S|-1)}{2}\right)-(m-\chi)=\frac{1}{2}\left(\sum_{S\in\mathcal{P}}|S|^{2}\right)-\left(\sum_{S\in\mathcal{P}}\frac{|S|}{2}\right)-m+\chi$
$\displaystyle=\frac{1}{2}\left(\sum_{S\in\mathcal{P}}|S|^{2}\right)-\frac{n}{2}-m+\chi.$

By Cauchy-Schwarz, we have
$\sum_{S\in\mathcal{P}}|S|^{2}\geqslant\frac{1}{|\mathcal{P}|}\cdot\left(\sum_{S\in\mathcal{P}}|S|\right)^{2}=\frac{n^{2}}{|\mathcal{P}|}$.
This bounds the intra-cluster cost from below by
$\psi\geqslant\frac{n^{2}}{2|\mathcal{P}|}-\frac{n}{2}-m+\chi$.

For the second statement, assume all clusters of $\mathcal{P}$ to be of size
$\frac{n}{|\mathcal{P}|}$. Then, there are
$\frac{1}{2}\cdot\frac{n}{|\mathcal{P}|}\cdot\left(\frac{n}{|\mathcal{P}|}-1\right)$
pairs of vertices in each cluster. Thereby, we have

$\psi=|\mathcal{P}|\cdot\frac{1}{2}\cdot\frac{n}{|\mathcal{P}|}\cdot\left(\frac{n}{|\mathcal{P}|}-1\right)-(m-\chi)=\frac{n^{2}}{2|\mathcal{P}|}-\frac{n}{2}-m+\chi.$

We further show that no clustering with clusters of unequal size achieves the
lower bound given by 7.6.

######  Lemma 7.8.

Let $G=(V,E)$ be an $n$-vertex $m$-edge graph and $\mathcal{P}$ a partition of
$V$ with an inter-cluster cost of $\chi$ such that there is a cluster
$S\in\mathcal{P}$ with $|S|=\frac{n}{|\mathcal{P}|}+a$ for some $a\geqslant
0$. Then, the intra-cluster cost of $\mathcal{P}$ is
$\psi\geqslant\frac{a^{2}|\mathcal{P}|}{2|\mathcal{P}|-2}+\frac{n^{2}}{2|\mathcal{P}|}-\frac{n}{2}-m+\chi$.

######  Proof 7.9.

If $a=0$, the statement is implied by 7.6. So, assume $a>0$. We write the
intra-cluster cost as

$\displaystyle\psi=\frac{1}{2}\cdot\left(\frac{n}{|\mathcal{P}|}+a\right)\cdot\left(\frac{n}{|\mathcal{P}|}+a-1\right)+\psi_{\text{rest}}$

with $\psi_{\text{rest}}$ being the intra-cluster cost incurred by
$\mathcal{P}\setminus\\{S\\}$. By applying 7.6 on
$\mathcal{P}\setminus\\{S\\}$, we have

$\displaystyle\psi$
$\displaystyle\geqslant\frac{1}{2}\cdot\left(\frac{n}{|\mathcal{P}|}+a\right)\cdot\left(\frac{n}{|\mathcal{P}|}+a-1\right)+\frac{\left(n-(\frac{n}{|\mathcal{P}|}+a)\right)^{2}}{2(|\mathcal{P}|-1)}-\frac{n-(\frac{n}{|\mathcal{P}|}+a)}{2}-m+\chi$
$\displaystyle=\frac{n^{2}}{2|\mathcal{P}|^{2}}+\frac{an}{|\mathcal{P}|}+\frac{a^{2}}{2}-\frac{n}{2|\mathcal{P}|}-\frac{a}{2}+\frac{n^{2}-2n^{2}/|\mathcal{P}|-2an+n^{2}/|\mathcal{P}|^{2}+2a\frac{n}{|\mathcal{P}|}+a^{2}}{2|\mathcal{P}|-2}$
$\displaystyle\hphantom{=}-\frac{n}{2}+\frac{n}{2|\mathcal{P}|}+\frac{a}{2}-m+\chi.$

Bringing the first summands to a common denominator of $2|\mathcal{P}|-2$
yields

$\displaystyle\psi$
$\displaystyle\geqslant\left(\frac{n^{2}(|\mathcal{P}|-1)}{|\mathcal{P}|^{2}}+\frac{an(2|\mathcal{P}|-2)}{|\mathcal{P}|}+a^{2}(|\mathcal{P}|-1)+n^{2}-\frac{2n^{2}}{|\mathcal{P}|}-2an+\frac{n^{2}}{|\mathcal{P}|^{2}}+\frac{2an}{|\mathcal{P}|}+a^{2}\right)$
$\displaystyle\hphantom{\geqslant}\hphantom{}\big{/}(2|\mathcal{P}|-2)-\frac{n}{2}-m+\chi$
$\displaystyle=\left(\frac{n^{2}|\mathcal{P}|}{|\mathcal{P}|^{2}}+\frac{2an|\mathcal{P}|}{|\mathcal{P}|}+a^{2}|\mathcal{P}|+n^{2}-\frac{2n^{2}}{|\mathcal{P}|}-2an\right)\big{/}(2|\mathcal{P}|-2)-\frac{n}{2}-m+\chi$
$\displaystyle=\left(-\frac{n^{2}}{|\mathcal{P}|}+a^{2}|\mathcal{P}|+n^{2}\right)\big{/}(2|\mathcal{P}|-2)-\frac{n}{2}-m+\chi.$

We then add
$0=-\frac{n^{2}}{2|\mathcal{P}|}\cdot\frac{2|P|-2}{2|P|-2}+\frac{n^{2}}{2|\mathcal{P}|}$
and obtain

$\displaystyle\psi$
$\displaystyle\geqslant\left(-\frac{n^{2}}{|\mathcal{P}|}+a^{2}|\mathcal{P}|+n^{2}-\frac{n^{2}(|\mathcal{P}|-1)}{|\mathcal{P}|}\right)\big{/}(2|\mathcal{P}|-2)+\frac{n^{2}}{2|\mathcal{P}|}-\frac{n}{2}-m+\chi$
$\displaystyle=\frac{a^{2}|\mathcal{P}|}{2|\mathcal{P}|-2}+\frac{n^{2}}{2|\mathcal{P}|}-\frac{n}{2}-m+\chi.$

Observe that as $|\mathcal{P}|>1$ and $a\neq 0$ this means that such a
clustering never achieves the lower bound given by 7.6. In particular, this
means that for fixed inter-cluster costs in minimum-cost fair clusterings in
forests all clusters are of equal size. This way, we are able to transfer some
hardness results obtained for exact fairness to relaxed fairness.

######  Theorem 7.10.

For every choice of $0<p_{1}\leqslant\frac{1}{c+1}\leqslant q_{1}<1$ and
$0<p_{2}\leqslant\frac{c}{c+1}\leqslant q_{2}<1$, _Relaxed 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 7.11.

We reduce from 3-Partition. Recall that there are $3p$ values
$a_{1},a_{2},\ldots,a_{3p}$ and the task is to partition them in triplets that
each sum to $B$. We construct a forest $F$ as follows. For every $a_{i}$ we
construct an arbitrary 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 relaxed fair clustering $\mathcal{P}$
such that

$\text{cost}(\mathcal{P})\leqslant 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 an exactly fair
partition, which is thus also relaxed fair. 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 relaxed fair clustering
$\mathcal{P}$ such that $\text{cost}(\mathcal{P})\leqslant
p\cdot\frac{B(B+1)}{2}-p(B-3)$. We prove that this clustering has to be not
just relaxed fair but exactly fair. Note that $|V|=p(B+1)$ and $|E|=p(B-3)$.
As the inter-cluster cost $\chi$ is non-negative, by 7.6 the intra-cluster
cost has a lower bound of

$\displaystyle\psi\geqslant\frac{(p(B+1))^{2}}{2|\mathcal{P}|}-\frac{p(B+1)}{2}-p(B-3).$

As there are exactly $p$ blue vertices and the relaxed fairness constraint
requires putting at least one blue vertex in each cluster, we have
$|\mathcal{P}|\leqslant p$. Hence,

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

This implies that the inter-cluster cost of $\mathcal{P}$ is 0 and
$|\mathcal{P}|=p$. 7.8 then gives that all clusters in $\mathcal{P}$ consist
of exactly $B+1$ vertices. As each of the $p$ clusters has at least 1 blue
vertex and there are $p$ blue vertices in total, we know that each cluster
consists of 1 blue and $B$ red vertices. Since all trees are of size greater
than $\frac{B}{4}$ and less than $\frac{B}{2}$, this implies 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.

Indeed, we note that we obtain our hardness result for any fairness constraint
that allows the exactly fair solution and enforces at least 1 vertex of each
color in every cluster. The same holds when transferring our hardness proof
for trees of diameter 4.

######  Theorem 7.12.

For every choice of $0<p_{1}\leqslant\frac{1}{c+1}\leqslant q_{1}<1$ and
$0<p_{2}\leqslant\frac{c}{c+1}\leqslant q_{2}<1$, _Relaxed Fair Correlation
Clustering_ on trees with diameter 4 and two colors in a ratio of $1:c$ is NP-
hard.

######  Proof 7.13.

We reduce from 3-Partition. We assume $B^{2}>16p$. We can do so as we obtain
an equivalent instance of 3-Partition when multiplying all $a_{i}$ and $B$ by
the same factor, here some value in $\mathrm{O}(p)$. 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. Note that the ratio
between blue and red vertices is $1:B$. We now show that there is a relaxed
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 an exact fair partition, which is thus also relaxed fair. We first
compute the inter-cluster cost. 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

$\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

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

For the other direction, assume there is a relaxed fair clustering
$\mathcal{P}$ such that
$\text{cost}(\mathcal{P})\leqslant\frac{pB^{2}-pB}{2}+7p-7$. We prove that
this clustering is not just relaxed fair but exactly fair.

To this end, we first show $|\mathcal{P}|=p$. Because each cluster requires
one of the $p$ blue vertices, we have $|\mathcal{P}|\leqslant p$. Now, let
$\chi$ denote the inter-cluster cost of $\mathcal{P}$. Note that $|V|=p(B+1)$
and $|E|=p(B-3)+3p+p-1=p(B+1)-1$. Then, by 7.6, we have

$\displaystyle\psi$
$\displaystyle\geqslant\frac{\left(p(B+1)\right)^{2}}{2|\mathcal{P}|}-\frac{p(B+1)}{2}-\left(p(B+1)-1\right)+\chi$
$\displaystyle=\frac{p^{2}B^{2}+2p^{2}B+p^{2}}{2|\mathcal{P}|}-\frac{3p(B+1)}{2}+1+\chi.$
(2)

Note that the lower bound is decreasing in $|\mathcal{P}|$. If we had
$|\mathcal{P}|\leqslant p-1$, then

$\displaystyle\psi\geqslant\frac{p^{2}B^{2}+2p^{2}B+p^{2}}{2(p-1)}-\frac{3p(B+1)}{2}+1+\chi.$

As the inter-cluster cost $\chi$ is non-negative, we would thereby get

$\displaystyle\text{cost}(\mathcal{P})$
$\displaystyle\geqslant\frac{p^{2}B^{2}+2p^{2}B+p^{2}}{2(p-1)}-\frac{3p(B+1)}{2}+1+\chi$
$\displaystyle\geqslant\frac{p^{2}B^{2}+2p^{2}B+p^{2}}{2(p-1)}-\frac{3p^{2}B-3pB+3p^{2}-3p}{2(p-1)}+\frac{2p-2}{2(p-1)}$
$\displaystyle\geqslant\frac{p^{2}B^{2}-p^{2}B-2p^{2}+3pB+5p-2}{2(p-1)}.$

However, we know

$\displaystyle\text{cost}(\mathcal{P})$
$\displaystyle\leqslant\frac{pB^{2}-pB}{2}+7p-7$
$\displaystyle=\frac{p^{2}B^{2}-pB^{2}-p^{2}B+pB+14p^{2}-14p-14p+14}{2(p-1)}$
$\displaystyle=\frac{p^{2}B^{2}-pB^{2}-p^{2}B+pB+14p^{2}-28p+14}{2(p-1)}.$

Hence, $|\mathcal{P}|\leqslant p-1$ holds only if $-2p^{2}+3pB+5p-2\leqslant-
pB^{2}+pB+14p^{2}-28p+14$ which is equivalent to
$pB^{2}-16p^{2}+2pB+33p-16\leqslant 0$. As we assume $B^{2}>16p$, this is
always false, so $|\mathcal{P}|=p$. Plugging this into Equation 2 yields

$\psi\geqslant\frac{pB^{2}+2pB+p}{2}-\frac{3p(B+1)}{2}+1+\chi=\frac{pB^{2}-pB}{2}-p+1+\chi.$

As $\text{cost}(\mathcal{P})=\chi+\psi$, we have

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

which yields $\chi\leqslant 4p-4$.

As no two blue vertices are placed in the same cluster, the cuts between blue
vertices incur an inter-cluster cost of exactly $p-1$. To estimate the number
of cut blue-red edges, let $a$ denote the number of red center vertices placed
in the cluster of the blue center vertex $v$. Then, there are $3p-a$ of the
$3p$ red edges cut. Let $\chi_{r}$ denote the number of cut red edges. Note
that $\chi=p-1+3p-a+\chi_{r}=4p-a-1+\chi_{r}$.

We prove that $a=3$. As $\chi\leqslant 4p-4$ we have $\chi_{r}-a\leqslant-3$,
whence $a\geqslant 3$. Next, we bound $\chi_{r}$ by $a$. Let
$\delta\in\mathbb{Z}$ be such that $B+\delta$ is the number of red vertices in
the cluster containing the blue center vertex $v$. Then,

$\chi_{r}\geqslant\frac{aB}{4}-(B+\delta-a)=\frac{(a-4)B}{4}-\delta+a$

as each red center vertex is connected to at least $\frac{B}{4}$ red leaves
but in the cluster of $v$ there is only space for $B+\delta-a$ of them. First,
assume $\delta\leqslant 0$. This implies
$\chi_{r}-a\geqslant\frac{(a-4)B}{4}$. As we required $\chi_{r}-a\leqslant-3$,
this gives $a<4$, as desired.

The case $\delta\geqslant 1$ is a bit more involved. From 7.8,
$p=|\mathcal{P}|$, and $m=n-1=p(B+1)-1$, we get

$\psi\geqslant\frac{\delta^{2}|\mathcal{P}|}{2|\mathcal{P}|-2}+\frac{\left(p(B+1)\right)^{2}}{2|\mathcal{P}|}-\frac{p(B+1)}{2}-m+\chi=\frac{\delta^{2}p}{2p-2}+\frac{pB^{2}+2pB+p}{2}-\frac{3p(B+1)}{2}+\chi+1.$

This yields

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

We derive from this inequality that $\chi\leqslant
4p-4-\frac{\delta^{2}p}{4p-4}$ and
$\chi_{r}-a\leqslant-3-\frac{\delta^{2}p}{4p-4}$ implying

$\frac{(a-4)B}{4}-\delta\leqslant-3-\frac{\delta^{2}p}{4p-4}$

The right-hand side is decreasing in $\delta$, and by plugging in the minimum
value for the case $\delta\geqslant 1$, we finally get
$\frac{(a-4)B}{4}\leqslant-2-\frac{p}{4p-4}$. This shows that $a<4$ must hold
here as well.

Thus, we have proven $a=3$, which also gives $\chi_{r}=0$ and $\chi=4p-4$. So,
not only do we have that
$\text{cost}(\mathcal{P})\leqslant\frac{pB^{2}-pB}{2}+7p-7$ but
$\text{cost}(\mathcal{P})=\frac{pB^{2}-pB}{2}+7p-7$. In Equation 3 we see that
for $\chi=4p-4$ this hits exactly the lower bound established by 7.6. Hence,
by 7.8, this implies that all clusters consist of exactly 1 blue and $B$ red
vertices and the clustering is exactly fair.

As $\chi_{r}=0$, all red stars are complete. 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.

In the hardness proofs in this section, we argued that for the constructed
instances clusterings that are relaxed fair, but not exactly fair would have a
higher cost than exactly fair ones. However, this is not generally true. It
does not even hold when limited to paths and two colors in a $1:1$ ratio, as
illustrated in Figure 11.

Figure 11: Exemplary path with a color ratio of $1:1$ where there is a
$\frac{2}{3}$-relaxed fair clustering of cost 3 (marked by the orange lines)
and the cheapest exactly fair clustering costs 4.

Because of this, we have little hope to provide a general scheme that
transforms all our hardness proofs from section 5 to the relaxed fairness
setting at once. Thus, we have to individually prove the hardness results in
this setting as done for Theorems 7.10 and 7.12. We are optimistic that the
other hardness results still hold in this setting, especially as the
construction for Theorem 5.5 is similar to the ones employed in this section.
We leave the task of transferring these results to future work.

###  7.3 Algorithms for Relaxed Fairness

We are also able to transfer the algorithmic result of Theorem 6.12 to a
specific $\alpha$-relaxed fairness setting. We exploit that the algorithm does
not really depend on exact fairness but on the fact that there is an upper
bound on the cluster size, which allows us to compute respective splittings.
In the following, we show that such upper bounds also exist for
$\alpha$-relaxed fairness with two colors in a ratio of $1:1$ and adapt the
algorithm accordingly. To compute the upper bound, we first prove 7.14, which
analogously to 2.2 bounds the size of clusters but in uncolored forests. Using
this lemma, with 7.16, we then prove an upper bound on the cluster size in
minimum-cost $\alpha$-relaxed fair clusterings for forests with two colors in
ratio $1:1$.

######  Lemma 7.14.

Let $F=(V,E)$ be an $n$-vertex $m$-edge forest and let
$\mathcal{P}_{1}=\\{V\\}$. Further, let $S\subset V$ with $4<|S|\leqslant n-3$
and let $\mathcal{P}_{2}=\\{S,V\setminus S\\}$. Then,
$\text{cost}(\mathcal{P}_{1})>\text{cost}(\mathcal{P}_{2})$.

######  Proof 7.15.

We have $\text{cost}(\mathcal{P}_{1})=\frac{n(n-1)}{2}-m$ as there are
$\frac{n(n-1)}{2}$ pairs of vertices and $m$ edges, none of which is cut by
$\mathcal{P}_{1}$. In the worst case, $\mathcal{P}_{2}$ cuts all of the at
most $n-1$ edges in the forest. It has one cluster of size $|S|$ and one of
size $n-|S|$, so

$\displaystyle\text{cost}(\mathcal{P}_{2})$ $\displaystyle\leqslant
n-1+\frac{(n-|S|)(n-|S|-1)}{2}+\frac{|S|(|S|-1)}{2}-(m-n-1)$
$\displaystyle=\frac{n(n-1)}{2}+\frac{-2n|S|+|S|^{2}+|S|}{2}+\frac{|S|^{2}-|S|}{2}-m+2n-2$
$\displaystyle=\frac{n(n-1)}{2}-n|S|+|S|^{2}-m+2n-2.$

Then, we have

$\displaystyle\text{cost}(\mathcal{P}_{1})-\text{cost}(\mathcal{P}_{2})$
$\displaystyle\geqslant n|S|-|S|^{2}-2n+2\geqslant(|S|-2)n-|S|^{2}+2.$

Note that the bound is increasing in $n$. As we have, $n\geqslant|S|+3$ and
$|S|>4$, this gives

$\text{cost}(\mathcal{P}_{1})-\text{cost}(\mathcal{P}_{2})\geqslant(|S|-2)(|S|+3)-|S|^{2}+2=|S|-4>0.$

With the knowledge of when it is cheaper to split a cluster, we now prove that
also for $\alpha$-relaxed Fair Correlation Clustering there is an upper bound
on the cluster size in minimum-cost solutions in forests. The idea is to
assume a cluster of a certain size and then argue that we can split it in a
way that reduces the cost and keeps $\alpha$-relaxed fairness.

######  Lemma 7.16.

Let $F$ be a forest with two colors in a ratio of $1:1$. Let $0<\alpha<1$ and
let $\hat{\alpha}\in\mathbb{N}$ be minimal such that
$\frac{2\hat{\alpha}}{\alpha}\in\mathbb{N}$ and
$\frac{2\hat{\alpha}}{\alpha}>4$. Then, if $\mathcal{P}$ is a minimum-cost
$\alpha$-relaxed fair clustering on $F$, we have
$|S|<4\frac{\hat{\alpha}}{\alpha^{2}}$ for all $S\in\mathcal{P}$.

######  Proof 7.17.

Assume otherwise, i.e., there is a cluster $S$ with $|S|\geqslant
4\frac{\hat{\alpha}}{\alpha^{2}}$. Let $b$ and $r$ denote the number of blue
and red vertices in $S$, respectively, and assume w.l.o.g. that $b\leqslant
r$. Because $|S|\geqslant 4\frac{\hat{\alpha}}{\alpha^{2}}$ we have
$\frac{\alpha}{2}\geqslant\frac{2\hat{\alpha}}{\alpha|S|}$. Due to the
$\alpha$-relaxed fairness constraint, this yields
$\frac{b}{|S|}\geqslant\frac{2\hat{\alpha}}{\alpha|S|}$ and thereby
$r\geqslant b\geqslant\frac{2\hat{\alpha}}{\alpha}$.

Then, consider the clustering obtained by splitting off $\hat{\alpha}$ blue
and $\frac{2\hat{\alpha}}{\alpha}-\hat{\alpha}$ red vertices of from $S$ into
a new cluster $S_{1}$ and let $S_{2}=S\setminus S_{1}$. Note that we choose
$\hat{\alpha}$ in a way that this is possible, i.e., that both sizes are
natural numbers. As the cost induced by all edges with at most one endpoint in
$S$ remains the same and the cost induced by the edges with both endpoints in
$S$ decreases, as shown in 7.14, the new clustering is cheaper than
$\mathcal{P}$. As we now prove that the new clustering is also
$\alpha$-relaxed Fair, this contradicts the optimality of $\mathcal{P}$.

We first prove the $\alpha$-relaxed fairness of $S_{1}$. Regarding the blue
vertices, we have a portion of
$\frac{\hat{\alpha}}{\hat{\alpha}+\frac{2\hat{\alpha}}{\alpha}-\hat{\alpha}}=\frac{\alpha}{2}$
in $S_{1}$, which fits the $\alpha$-relaxed fairness constraint. Regarding the
red vertices, we have
$\frac{\frac{2\hat{\alpha}}{\alpha}-\hat{\alpha}}{\hat{\alpha}+\frac{2\hat{\alpha}}{\alpha}-\hat{\alpha}}=1-\frac{\alpha}{2}$,
which fits the $\alpha$-relaxed fairness constraint as $0<\alpha<1$, so
$1-\frac{\alpha}{2}\geqslant\frac{\alpha}{2}$ and
$1-\frac{\alpha}{2}=\frac{2\alpha-\alpha^{2}}{2\alpha}\leqslant\frac{1}{2\alpha}$.

Now we prove the $\alpha$-relaxed fairness of $S_{2}$. The portion of blue
vertices in $S_{2}$ is
$\frac{b-\hat{\alpha}}{r+b-\frac{2\hat{\alpha}}{\alpha}}$, so we have to show
that this value lays between $\frac{\alpha}{2}$ and $\frac{1}{2\alpha}$. We
start with showing the value is at least $\frac{\alpha}{2}$ by proving
$\frac{\alpha}{2}\cdot\left(r+b-\frac{2\hat{\alpha}}{\alpha}\right)\leqslant
b-\hat{\alpha}$. As $S$ is $\alpha$-relaxed fair, we have
$r\leqslant\frac{2b}{\alpha}-b$ because otherwise
$\frac{b}{b+r}<\frac{b}{b+\frac{2b}{\alpha}-b}=\frac{\alpha}{2}$. Hence, we
have

$\displaystyle\frac{\alpha}{2}\cdot\left(r+b-\frac{2\hat{\alpha}}{\alpha}\right)\leqslant\frac{\alpha}{2}\cdot\left(\frac{2b}{\alpha}-b+b-\frac{2\hat{\alpha}}{\alpha}\right)=b-\hat{\alpha}.$

Similarly, we show the ratio is at most $\frac{1}{2\alpha}$ by proving the
equivalent statement of $2\alpha(b-\hat{\alpha})\leqslant
r+b-\frac{2\hat{\alpha}}{\alpha}$. As we assume $r\geqslant b$, we have

$\displaystyle r+b-\frac{2\hat{\alpha}}{\alpha}\geqslant
2b-\frac{2\hat{\alpha}}{\alpha}\geqslant
2\left(b-\frac{\hat{\alpha}}{\alpha}-\left((1-\alpha)b+(\alpha^{2}-1)\frac{\hat{\alpha}}{\alpha}\right)\right)=2\alpha\left(b-\hat{\alpha}\right).$

The second step holds because we assumed
$b\geqslant\frac{2\hat{\alpha}}{\alpha}\geqslant\frac{\alpha\hat{\alpha}+\hat{\alpha}}{\alpha}=\frac{\frac{\hat{\alpha}}{\alpha}-\alpha\hat{\alpha}}{1-\alpha}$,
so we have $(1-\alpha)b+(\alpha^{2}-1)\frac{\hat{\alpha}}{\alpha}\geqslant 0$.
Now, we regard the portion of red vertices in $S_{2}$, which is
$\frac{r-\left(\frac{2\hat{\alpha}}{\alpha}-\hat{\alpha}\right)}{r+b-\frac{2\hat{\alpha}}{\alpha}}$.
We know that $r\geqslant\frac{2\hat{\alpha}}{\alpha}$, that is,
$(1-\alpha)r\geqslant\frac{2\hat{\alpha}}{\alpha}-2\hat{\alpha}$ or, in other
words,
$r-\left(\frac{2\hat{\alpha}}{\alpha}+\hat{\alpha}\right)\geqslant\alpha
r-\hat{\alpha}$. As $r\geqslant b$, this implies

$r-\left(\frac{2\hat{\alpha}}{\alpha}+\hat{\alpha}\right)\geqslant\frac{\alpha}{2}\cdot\left(r+b-\frac{2\hat{\alpha}}{\alpha}\right)$

and therefore
$\frac{r-\left(\frac{2\hat{\alpha}}{\alpha}-\hat{\alpha}\right)}{r+b-\frac{2\hat{\alpha}}{\alpha}}\geqslant\frac{\alpha}{2}$.

It remains to prove that this ratio is also at most $\frac{1}{2\alpha}$. We
have $r\geqslant\frac{2\hat{\alpha}}{\alpha}-\hat{\alpha}$, which is
equivalent to

$\left(2\alpha-1-\frac{\alpha}{2-\alpha}\right)r\leqslant
4\hat{\alpha}-2\alpha\hat{\alpha}-\frac{2\hat{\alpha}}{\alpha}.$

Note that
$2\alpha-1-\frac{\alpha}{2-\alpha}=-\frac{2\alpha^{2}-4\alpha+2}{2-\alpha}=-\frac{2(\alpha-1)^{2}}{2-\alpha}<0$
and that $r\leqslant\frac{2b}{\alpha}-b$ gives
$b\geqslant\frac{r}{\frac{2}{\alpha}-1}=\frac{\alpha r}{2-\alpha}$. With this,
the above inequality implies

$(2\alpha-1)r-b\leqslant
4\hat{\alpha}-2\alpha\hat{\alpha}-\frac{2\hat{\alpha}}{\alpha}$

From this, we finally arrive at
$2\alpha\cdot\left(r-\left(\frac{2\hat{\alpha}}{\alpha}-\hat{\alpha}\right)\right)\leqslant
r+b-\frac{2\hat{\alpha}}{\alpha}$, that is,
$\frac{r-\left(\frac{2\hat{\alpha}}{\alpha}-\hat{\alpha}\right)}{r+b-\frac{2\hat{\alpha}}{\alpha}}\leqslant\frac{1}{2\alpha}$.

This proves that both $S_{1}$ and $S_{2}$ are $\alpha$-relaxed fair. As
splitting $S$ into $S_{1}$ and $S_{2}$ remains $\alpha$-relaxed fair and is
cheaper, this contradicts $S$ being in a minimum-cost $\alpha$-relaxed fair
clustering.

We are now able to adapt the algorithm presented in subsection 6.3 to solve
Relaxed Fair Correlation Clustering on forests with two colors in a ratio of
$1:1$. While the original algorithm exploited that any optimum solution has
fair clusters of minimum size, with 7.16 we are able to bound the clusters
also in the $\alpha$-relaxed setting.

Like the original algorithm, we first create a list of possible splittings.
However, these splittings can contain not only components with one or two
vertices, as we know would suffice for the exact fairness with two colors in a
$1:1$ ratio, but each component may contain up to
$4\frac{\hat{\alpha}}{\alpha^{2}}$ vertices with $\hat{\alpha}$ being the
smallest natural number such that $\frac{2\hat{\alpha}}{\alpha}\in\mathbb{N}$
and $\frac{2\hat{\alpha}}{\alpha}>4$ as defined in 7.16. In the following, we
set $d=4\frac{\hat{\alpha}}{\alpha^{2}}$ to refer to this maximum size of a
cluster. In the second phase, it checks which of these splitting can be merged
into an $\alpha$-relaxed fair clustering and among these returns the one of
minimum cost.

##### Splitting the forest.

To get the optimal way to obtain a splitting of each possible coloring, we
simply apply 6.15 and set $d_{1}=d_{2}=d$ as we know the optimum solution has
to be among clusters with no more than $d$ vertices of either color. This
phase takes time in
$\mathrm{O}(n^{2(d+1)^{2}+2d+2}\cdot\left((d+1)^{2}\right)^{2d})=\mathrm{O}(n^{2d^{2}+6d+4}\cdot(d+1)^{4d})$.

##### Assembling a fair clustering.

In the second phase, we have to find a splitting in $D_{r}^{\emptyset}$ that
can be transformed into an $\alpha$-relaxed fair clustering and yields the
minimum Correlation Clustering cost. As we tracked the minimum inter-cluster
cost for each possible partition coloring of splittings in the first phase, we
do not have to consider cutting more edges in this phase, because for the
resulting splittings coloring we already have tracked a minimum inter-cluster
cost. Hence, the only questions are whether a splitting is _assemblable_ ,
i.e., whether its components can be merged such that it becomes an
$\alpha$-relaxed fair clustering, and, if so, what the cheapest way to do so
is.

Regarding the first question, observe that the _assemblability_ only depends
on the partition coloring of the splitting. Hence, it does not hurt that in
the first phase we tracked only all possible partition colorings of splittings
and not all possible splittings themselves. First, note that the coloring of a
splitting may itself yield an $\alpha$-relaxed fair clustering. We mark all
such partition colorings as assemblable, taking time in
$\mathrm{O}(n^{d^{2}+1})$. For the remaining partition colorings, we employ
the following dynamic program.

Recall that the size of a partition coloring refers to the number of set
colorings it contains (not necessarily the number of different set colorings).
We decide assemblability for all possible partition colorings from smallest to
largest. Note that each partition coloring is of size at least
$\lceil\frac{n}{d}\rceil$. If it is of size exactly $\lceil\frac{n}{d}\rceil$,
then there are no two set colorings that can be merged and still be of size at
most $d$, as all other set colorings are of size at most $d$. Hence, in this
case, a splitting is assemblable if and only if it is already an
$\alpha$-relaxed fair clustering so we have already marked the partition
colorings correctly. Now, assume that we decided assemblability for all
partition colorings of size $i\geqslant\lceil\frac{n}{d}\rceil$. We take an
arbitrary partition coloring $C$ of size $i+1$, which is not yet marked as
assemblable. Then, it is assemblable if and only if at least two of its set
colorings are merged together to form an $\alpha$-relaxed fair clustering. In
particular, it is assemblable if and only if there are two set colorings
$C_{1},C_{2}$ in $C$ such that the coloring $C^{\prime}$ obtained by removing
the set colorings $C_{1},C_{2}$ from $C$ and adding the set coloring of the
combined coloring of $C_{1}$ and $C_{2}$ is assemblable. Note that
$C^{\prime}$ is of size $i$. Given all assemblable partition colorings of size
$i$, we therefore find all assemblable partition colorings of size $i+1$ by
for each partition coloring of size $i$ trying each possible way to split one
of its set colorings into two. As there are at most $i^{d^{2}}$ partition
colorings of size $i$, this takes time in $\mathrm{O}(i^{d^{2}}\cdot i\cdot
2^{d})$. The whole dynamic program then takes time in
$\mathrm{O}(n^{d^{2}+1}\cdot 2^{d})\subseteq\mathrm{O}(n^{d^{2}+d+1})$.

It remains to answer how we choose the assembling yielding the minimum cost.
In the algorithm for exact fairness, we do not have to worry about that as
there we could assume that the Correlation Clustering cost only depends on the
inter-cluster cost. Here, this is not the case as the $\alpha$-relaxed
fairness allows clusters of varying size, so 2.1 does not apply. However,
recall that we can write the Correlation Clustering cost of some partition
$\mathcal{P}$ of the vertices as
$\sum_{S\in\mathcal{P}}\frac{|S|(|S-1|)}{2}+2\chi$, where $\chi$ is the inter-
cluster cost. The cost hence only depends on the inter-cluster cost and the
sizes of the clusters, which in turn depends on the partition coloring. To
compute the cost of a splitting, we take the inter-cluster cost computed in
the first phase for $\chi$. Once more, we neglect decreasing inter-cluster
cost due to the merging of clusters as the resulting splitting is also
considered in the array produced in the first phase. By an argument based on
the Cauchy-Schwarz Inequality, we see that merging clusters only increases the
value of $\sum_{S\in\mathcal{P}}\frac{|S|(|S-1|)}{2}$ as we have fewer but
larger squares. Hence, the cheapest cost obtainable from a splitting which is
itself $\alpha$-relaxed fair is just this very clustering. If a splitting is
assemblable but not $\alpha$-relaxed fair itself, the sum is the minimum among
all the values of the sums of $\alpha$-relaxed fair splittings it can be
merged into. This value is easily computed by not only passing down
assemblability but also the value of this sum in the dynamic program described
above and taking the minimum if there are multiple options for a splitting.
This does not change the running time asymptotically and the running time of
the second phase is dominated by the one of the first phase.

The complete algorithm hence runs in time in
$\mathrm{O}(n^{2d^{2}+6d+4}\cdot(d+1)^{4d})$.

######  Theorem 7.18.

Let $F$ be an $n$-vertex forest in which the vertices are colored with two
colors in a ratio of $1:1$. Then _$\alpha$ -relaxed Fair Correlation
Clustering_ on $F$ can be solved in time in
$\mathrm{O}(n^{2d^{2}+6d+4}\cdot(d+1)^{4d})$, where
$d=4\frac{\hat{\alpha}}{\alpha^{2}}$ and $\hat{\alpha}\in\mathbb{N}$ is
minimal such that $\frac{2\hat{\alpha}}{\alpha}\in\mathbb{N}$ and
$\frac{2\hat{\alpha}}{\alpha}>4$.

We are confident that 7.16 can be generalized such that for an arbitrary
number of colors in arbitrary ratios the maximum cluster size is bounded by
some function in $\alpha$ and the color ratio. Given the complexity of this
lemma for the $1:1$ case, we leave this task open to future work. If such a
bound is proven, then the algorithmic approach employed in Theorem 7.18 is
applicable to arbitrarily colored forests. Similarly, bounds on the cluster
size in the more general relaxed fair clusterings can be proven. As an
intermediate solution, we note that for Relaxed Fair Correlation Clustering we
can employ the approach used for $\alpha$-relaxed Fair Correlation Clustering
by setting $\alpha$ large enough to contain all allowed solutions and
filtering out solutions that do not match the relaxed fairness constraint in
the assembling phase. We do not give this procedure explicitly here as we
suspect for these cases it is more promising to calculate the precise upper
bound on the maximum cluster size and perform the algorithm accordingly
instead of reducing to the $\alpha$-relaxed variant.

##  8 Approximations

So far, we have concentrated on finding an optimal solution to Fair
Correlation Clustering in various instances. Approximation algorithms that do
not necessarily find an optimum but near-optimum solutions efficiently are
often used as a remedy for hard problems, for example, the 2.06-approximation
to (unfair) Correlation Clustering [17]. In this section, we find that just
taking any fair clustering is a quite close approximation and the
approximation becomes even closer to the optimum if the minimum size of any
fair cluster, as given by the color ratio, increases.

Formally, a problem is an optimization problem if for every instance $I$ there
is a set of permissible solutions $S(I)$ and an objective function $m\colon
S(I)\rightarrow\mathbb{R}_{>0}$ assigning a score to each solution. Then, some
$S\in S(I)$ is an optimal solution if it has the highest or lowest score among
all permissible solutions, depending on the problem definition. We call the
score of this solution $m^{*}\\!(I)$. For example, for Fair Correlation
Clustering, the instance is given by a graph with colored vertices, every fair
clustering of the vertices is a permissible solution, the score is the
Correlation Clustering cost, and the objective is to minimize this cost.888We
note that the clustering cost could be 0, which contradicts the definition
$m\colon S(I)\rightarrow\mathbb{R}_{>0}$. However, every 0-cost clustering
simply consists of the connected components of the graph. We do not consider
those trivial instances. An $\alpha$-approximation an optimization problem is
an algorithm that, for each instance $I$, outputs a permissible solution $S\in
S(I)$ such that
$\frac{1}{\alpha}\leqslant\frac{m(S)}{m^{*}\\!(I)}\leqslant\alpha$. For Fair
Correlation Clustering in particular, this means the algorithm outputs a fair
clustering with a cost of at most $\alpha$ times the minimum clustering cost.

APX is the class of problems that admit an $\alpha$-approximation with
$\alpha\in\mathrm{O}(1)$. A polynomial-time approximation scheme (PTAS), is an
algorithm that for each optimization problem instance as well as parameter
$\varepsilon>0$ computes a $(1+\varepsilon)$-approximation for a minimization
problem or a $(1-\varepsilon)$-approximation for a maximization problem in
time in $\mathrm{O}(n^{f(\varepsilon)})$, for some computable function $f$
depending only on $\varepsilon$. We use PTAS to refer to the class of
optimization problems admitting a PTAS. An optimization problem $L$ is called
APX-hard if every problem in APX has a PTAS-reduction to $L$, i.e., a PTAS for
$L$ implies there is a PTAS for every problem in APX. If $L$ is additionally
in APX itself, $L$ is called APX-complete. By definition, we have
$\textsf{PTAS}\subseteq\textsf{APX}$. Further, $\textsf{PTAS}\neq\textsf{APX}$
unless $\textsf{P}=\textsf{NP}$.

We find that taking _any_ fair clustering of a forest yields a good
approximation.

######  Theorem 8.1.

Let $F$ be an $n$-vertex $m$-edge forest with $k\geqslant 2$ colors in a ratio
of $c_{1}:c_{2}:\ldots:c_{k}$ and $d=\sum_{i=1}^{k}c_{i}\geqslant 4$. Then,
there is a
$\frac{\left(d^{2}-d\right)n+2dm}{\left(d^{2}-5d+4\right)n+2dm}$-approximation
for _Fair Correlation Clustering_ on $F$ computable in time in
$\mathrm{O}(n)$.

######  Proof 8.2.

By first sorting the vertices by color and then iteratively adding the next
$c_{i}$ vertices of each color $i$ to the next cluster, we obtain a fair
clustering $\mathcal{P}$ with clusters of size $d$ in linear time. In the
worst-case, $\mathcal{P}$ cuts all $m$ edges. Hence, by 2.1, we have

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

We compare this cost to the one of a minimum-cost fair clustering
$\mathcal{P}^{*}$. By 2.2, $\mathcal{P}^{*}$ to consist of clusters of size
$d$. Each of the $\frac{n}{d}$ clusters contains at most $d-1$ edges due to
the forest structure. Hence, at most $\frac{n}{d}\cdot(d-1)$ edges are placed
inside a cluster. Then, for the inter-cluster cost, we have $\chi\geqslant
m-\frac{n}{d}\cdot(d-1)=\frac{n}{d}-n+m$. 2.1 gives

$\text{cost}(\mathcal{P}^{*})\geqslant\frac{(d-1)n}{2}-m+2\left(\frac{n}{d}-n+m\right)=\frac{(d-5)n}{2}+\frac{2n}{d}+m.$

Thereby, $\mathcal{P}$ yields an $\alpha$-approximation to Fair Correlation
Clustering, where

$\displaystyle\alpha$
$\displaystyle=\left(\frac{(d-1)n}{2}+m\right)\big{/}\left(\frac{(d-5)n}{2}+\frac{2n}{d}+m\right)$
$\displaystyle=\left(\frac{\left(d^{2}-d\right)n+2dm}{2d}\right)\big{/}\left(\frac{\left(d^{2}-5d+4\right)n+2dm}{2d}\right)=\frac{\left(d^{2}-d\right)n+2dm}{\left(d^{2}-5d+4\right)n+2dm}.$

Observe that $\alpha$ is decreasing in $d$ for $d\geqslant 4$ and converges to
1 as $d\rightarrow\infty$. Further, for $d=5$ we obtain
$\alpha=\frac{20n+10m}{4n+10m}<5$. Thus, for $d\geqslant 5$ we have a
5-approximation to Fair Correlation Clustering on forests. For $d=4$, $\alpha$
becomes linear in $\frac{m}{n}$ and for smaller $d$ it is not necessarily
positive or not even defined if $\left(d^{2}-5d+4\right)n+2dm=0$. This is
because if there are very small clusters, then in forests there are solutions
of almost no cost. If $d=2$, i.e., there are two colors in a $1:1$ ratio,
there are even forests with a cost of 0, namely the ones where all vertices
have degree 1 and each edge connects 2 vertices of different colors. A
solution cutting every edge is then much worse than an optimum solution. If
the factor becomes negative or not defined, this is due to us bounding the
inter-cluster cost of the optimum clustering by $\frac{n}{d}-n+m$, which is
possibly negative, while the inter-cluster cost is guaranteed to be non-
negative.

On trees, however, if the clusters are small even an optimum solution has to
cut some edges as now there always are edges between the clusters. Hence, in
this case, we obtain a good approximation for all possible $d$. Note that the
proof of Theorem 8.1 does not really require $d\geqslant 4$ but for $d<4$ the
approximation factor is just not helpful or defined. This changes, if we
assume the forest to be a tree and plug in $m=n-1$.

######  Corollary 8.3.

Let $T$ be an $n$-vertex tree with $k\geqslant 2$ colors in a ratio of
$c_{1}:c_{2}:\ldots:c_{k}$ and $d=\sum_{i=1}^{k}c_{i}$. Then, there is a
$\frac{\left(d^{2}+d\right)n-2d}{\left(d^{2}-3d+4\right)n-2d}$-approximation
to _Fair Correlation Clustering_ on $T$ that is computed in time in
$\mathrm{O}(n)$.

Now, the approximation factor is still decreasing in $d$ and converges to 1 as
$d\rightarrow\infty$. However, it is positive and defined for all $d\geqslant
2$. For $d=2$ we obtain $\frac{6n-4}{2n-4}<3$. Therefore, we have a
3-approximation to Fair Correlation Clustering on trees.

Nevertheless, our results for forest suffice to place Fair Correlation
Clustering in APX and even in PTAS. First, for $d\geqslant 5$ we have a
5-approximation to Fair Correlation Clustering on forests. If $d\leqslant 4$,
a minimum-cost fair clustering is found on the forest in polynomial time by
Theorem 6.12. Hence, Fair Correlation Clustering on forests is in APX. Next,
recall that the larger the minimum fair cluster size $d$, the better the
approximation becomes. Recall that our dynamic program for Theorem 6.12 has
better running time the smaller the value $d$. By combining these results, we
obtain a PTAS for Fair Correlation Clustering on forests. This contrasts Fair
Correlation Clustering on general graphs, as even unfair Correlation
Clustering is APX-hard there [16] and therefore does not admit a PTAS unless
$\textsf{P}=\textsf{NP}$.

######  Theorem 8.4.

There is a PTAS for _Fair Correlation Clustering_ on forests. Moreover, an
$(1{+}\varepsilon)$-approximate fair clustering can be computed in time
$\mathrm{O}(n^{\emph{{poly}}(1/\varepsilon)})$.

######  Proof 8.5.

If $d\leqslant 4$, we find a minimum-cost fair clustering in polynomial time
by Theorem 6.12. Else, if
$\frac{\left(d^{2}-d\right)n+2dm}{\left(d^{2}-5d+4\right)n+2dm}\leqslant
1+\varepsilon$, it suffices to return any fair clustering by Theorem 8.1.
Otherwise, we have $d\geqslant 5$ and

$1+\varepsilon<\frac{\left(d^{2}-d\right)n+2dm}{\left(d^{2}-5d+4\right)n+2dm}<\frac{\left(d^{2}-d\right)n}{\left(d^{2}-5d\right)n}=\frac{d-1}{d-5}.$

It follows that, $d-5+d\varepsilon-5\varepsilon<d-1$, which simplifies to
$d<\frac{4}{\varepsilon}+5$. Hence, by Theorem 6.12, we find a minimum-cost
fair clustering in time in $\mathrm{O}(n^{f(\varepsilon)})$ for some
computable function $f$ independent from $n$. In all cases, we find a fair
clustering with a cost of at most $1+\varepsilon$ times the minimum
Correlation Clustering cost and take time in $\mathrm{O}(n^{f(\varepsilon)})$,
giving a PTAS.

To show that $f$ is in fact bounded by a polynomial in
$\nicefrac{{1}}{{\varepsilon}}$, we only need to look at the third case
(otherwise $f$ is constant). The bound $d<\frac{4}{\varepsilon}+5$ and
$d=\sum_{i=1}^{k}c_{i}$ together imply the the number of colors $k$ is
constant w.r.t. $n$. Under this condition, the exponent of the running time in
Theorem 6.12 is a polynomial in $d$ and thus in
$\nicefrac{{1}}{{\varepsilon}}$.

## References

  * [1] Saba Ahmadi, Sainyam Galhotra, Barna Saha, and Roy Schwartz.  Fair correlation clustering.  CoRR, arXiv:2002.03508, 2020.  ArXiv preprint.  URL: https://arxiv.org/abs/2002.03508.
  * [2] Sara Ahmadian, Alessandro Epasto, Ravi Kumar, and Mohammad Mahdian.  Fair correlation clustering.  In Proceedings of the 23rd Conference on Artificial Intelligence and Statistics (AISTATS), page 4195–4205, 2020.  URL: https://proceedings.mlr.press/v108/ahmadian20a.html.
  * [3] Sara Ahmadian and Maryam Negahbani.  Improved approximation for fair correlation clustering.  CoRR, abs/2206.05050, 2022.  doi:10.48550/arXiv.2206.05050.
  * [4] Nir Ailon, Moses Charikar, and Alantha Newman.  Aggregating inconsistent information: Ranking and clustering.  Journal of the ACM, 55(5):23:1–23:27, 2008.  doi:10.1145/1411509.1411513.
  * [5] Noga Alon.  Splitting necklaces.  Advances in Mathematics, 63(3):247–253, 1987.  doi:10.1016/0001-8708(87)90055-7.
  * [6] Noga Alon and Douglas B. West.  The Borsuk-Ulam theorem and bisection of necklaces.  Proceedings of the American Mathematical Society, 98(4):623–628, 1986.  doi:10.2307/2045739.
  * [7] Sayan Bandyapadhyay, Fedor V. Fomin, and Kirill Simonov.  On coresets for fair clustering in metric and euclidean spaces and their applications.  In Proceedings of the 48th International Colloquium on Automata, Languages, and Programming (ICALP), pages 23:1–23:15, 2021.  doi:10.4230/LIPIcs.ICALP.2021.23.
  * [8] Nikhil Bansal, Avrim Blum, and Shuchi Chawla.  Correlation clustering.  Machine Learning, 56(1–3):89–113, 2004.  doi:10.1023/B:MACH.0000033116.57574.95.
  * [9] Lucas Bastos, Luiz Satoru Ochi, Fábio Protti, Anand Subramanian, Ivan César Martins, and Rian Gabriel S. Pinheiro.  Efficient algorithms for cluster editing.  Journal of Combinatorial Optimization, 31(1):347–371, 2016.  doi:10.1007/s10878-014-9756-7.
  * [10] Amir Ben-Dor, Ron Shamir, and Zohar Yakhini.  Clustering gene expression patterns.  Journal of Computational Biology, 6(3–4):281–297, 1999.  doi:10.1089/106652799318274.
  * [11] Suman K. Bera, Deeparnab Chakrabarty, Nicolas J. Flores, and Maryam Negahbani.  Fair algorithms for clustering.  In Proceedings of the 33rd Conference on Neural Information Processing Systems (NeurIPS), page 4954–4965, 2019.
  * [12] Ioana Oriana Bercea, Martin Groß, Samir Khuller, Aounon Kumar, Clemens Rösner, Daniel R. Schmidt, and Melanie Schmidt.  On the cost of essentially fair clusterings.  In Proceedings of the 2019 Conference on Approximation for Combinatorial Optimization Problems and the 2019 Conference on Randomization in Computation (APPROX/RANDOM), volume 145 of LIPIcs, pages 18:1–18:22, 2019.
  * [13] Francesco Bonchi, David García-Soriano, and Francesco Gullo.  Correlation Clustering.  Morgan & Claypool Publishers, 2022.  doi:10.2200/S01163ED1V01Y202201DMK019.
  * [14] Paul Simon Bonsma, Thomas Epping, and Winfried Hochstättler.  Complexity results on restricted instances of a paint shop problem for words.  Discrete Applied Mathematics, 154(9):1335–1343, 2006.  doi:10.1016/j.dam.2005.05.033.
  * [15] Sebastian Böcker and Jan Baumbach.  Cluster editing.  In Proceedings of the 9th Conference on Computability in Europe (CiE), page 33–44, 2013.  doi:10.1007/978-3-642-39053-1_5.
  * [16] Moses Charikar, Venkatesan Guruswami, and Anthony Wirth.  Clustering with qualitative information.  Journal of Computer and System Sciences, 71(3):360–383, 2005.  doi:10.1016/j.jcss.2004.10.012.
  * [17] Shuchi Chawla, Konstantin Makarychev, Tselil Schramm, and Grigory Yaroslavtsev.  Near optimal LP rounding algorithm for correlation clustering on complete and complete $k$-partite graphs.  In Proceedings of the 47th Symposium on Theory of Computing (STOC), page 219–228, 2015.  doi:10.1145/2746539.2746604.
  * [18] Li Chen, Rasmus Kyng, Yang P. Liu, Richard Peng, Maximilian Probst Gutenberg, and Sushant Sachdeva.  Maximum Flow and Minimum-Cost Flow in Almost-Linear Time.  In Proceedings of the 63rd Symposium on Foundations of Computer Science (FOCS), pages 612–623, 2022.  doi:10.1109/FOCS54457.2022.00064.
  * [19] Flavio Chierichetti, Ravi Kumar, Silvio Lattanzi, and Sergei Vassilvitskii.  Fair clustering through fairlets.  In Proceedings of the 31st Conference on Neural Information Processing Systems (NeurIPS), page 5036–5044, 2017.
  * [20] Vincent Cohen-Addad, Euiwoong Lee, and Alantha Newman.  Correlation Clustering with Sherali-Adams.  In Proceedings of the 63rd Symposium on Foundations of Computer Science (FOCS), pages 651–661. IEEE, 2022.  doi:10.1109/FOCS54457.2022.00068.
  * [21] Marek Cygan, Marcin Mucha, Karol Węgrzycki, and Michał Włodarczyk.  On problems equivalent to (min,+)-convolution.  ACM Transactions on Algorithms, 15(1):14:1–14:25, 2019.  doi:10.1145/3293465.
  * [22] Julien Darlay, Nadia Brauner, and Julien Moncel.  Dense and sparse graph partition.  Discrete Applied Mathematics, 160(16):2389–2396, 2012.  doi:10.1016/j.dam.2012.06.004.
  * [23] Michael Dinitz, Aravind Srinivasan, Leonidas Tsepenekas, and Anil Vullikanti.  Fair disaster containment via graph-cut problems.  In Proceedings of the 25th Conference on Artificial Intelligence and Statistics (AISTATS), page 6321–6333, 2022.  URL: https://proceedings.mlr.press/v151/dinitz22a.html.
  * [24] Thomas Epping, Winfried Hochstättler, and Peter Oertel.  Complexity results on a paint shop problem.  Discrete Applied Mathematics, 136:2-3:217–226, 2004.  doi:10.1016/S0166-218X(03)00442-6.
  * [25] Seyed A. Esmaeili, Brian Brubach, Leonidas Tsepenekas, and John P. Dickerson.  Probabilistic fair clustering.  In Proceedings of the 34th Conference on Neural Information Processing Systems (NeurIPS), page 12743–12755, 2020.
  * [26] Michael Feldman, Sorelle A. Friedler, John Moeller, Carlos Scheidegger, and Suresh Venkatasubramanian.  Certifying and removing disparate impact.  In Proceedings of the 21th ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD), page 259–268, 2015.  doi:10.1145/2783258.2783311.
  * [27] Andreas E. Feldmann and Luca Foschini.  Balanced partitions of trees and applications.  Algorithmica, 71(2):354–376, 2015.  doi:10.1007/s00453-013-9802-3.
  * [28] Zachary Friggstad and Ramin Mousavi.  Fair correlation clustering with global and local guarantees.  In Proceedings of the 2021 Workshop on Algorithms and Data Structures (WADS), page 414–427, 2021.  doi:10.1007/978-3-030-83508-8_30.
  * [29] Michael R. Garey and David S. Johnson.  Computers and intractability: A guide to the theory of NP-completeness.  W. H. Freeman, 1979.
  * [30] Jonggyu Jang and Hyun Jong Yang.  $\alpha$-Fairness-maximizing user association in energy-constrained small cell networks.  IEEE Transactions on Wireless Communications, 21(9):7443–7459, 2022\.  doi:10.1109/TWC.2022.3158694.
  * [31] Suchi Kumari and Anurag Singh.  Fair end-to-end window-based congestion control in time-varying data communication networks.  International Journal of Communication Systems, 32(11), 2019.  doi:10.1002/dac.3986.
  * [32] Dana Pessach and Erez Shmueli.  A review on fairness in machine learning.  ACM Computing Surveys, 55(3):51:1–51:44, 2022.  doi:10.1145/3494672.
  * [33] Simon Régnier.  Sur quelques aspects mathématiques des problèmes de classification automatique.  Mathématiques et Sciences Humaines, 82:31–44, 1983.
  * [34] Melanie Schmidt, Chris Schwiegelshohn, and Christian Sohler.  Fair coresets and streaming algorithms for fair $k$-means.  In Proceedings of the 17th Workshop on Approximation and Online Algorithms (WAOA), page 232–251, 2020.  doi:10.1007/978-3-030-39479-0_16.
  * [35] Roy Schwartz and Roded Zats.  Fair correlation clustering in general graphs.  In Proceedings of the 2022 Conference on Approximation for Combinatorial Optimization Problems and the 2022 Conference on Randomization in Computation (APPROX/RANDOM), pages 37:1–37:19, 2022.  doi:10.4230/LIPIcs.APPROX/RANDOM.2022.37.
  * [36] Xiao Xin.  An FPT algorithm for the correlation clustering problem.  Key Engineering Materials, 474–476:924–927, 2011.  doi:10.4028/www.scientific.net/KEM.474-476.924.
  * [37] Charles T. Zahn, Jr.  Approximating symmetric relations by equivalence relations.  Journal of the Society for Industrial and Applied Mathematics, 12(4):840–847, 1964.  doi:10.1137/0112071.
  * [38] Imtiaz Masud Ziko, Jing Yuan, Eric Granger, and Ismail Ben Ayed.  Variational fair clustering.  In Proceedings of the 35th AAAI Conference on Artificial Intelligence (AAAI), page 11202–11209, 2021.  doi:10.1609/aaai.v35i12.17336.