Abstract
We consider the family of Correlation Clustering optimization problems under fairness constraints. In Correlation Clustering we are given a graph whose every edge is labeled either with a + or a , and the goal is to find a clustering that agrees the most with the labels: + edges within clusters and  edges across clusters. The notion of fairness implies that there is no over, or under, representation of vertices in the clustering: every vertex has a color and the distribution of colors within each cluster is required to be the same as the distribution of colors in the input graph. Previously, approximation algorithms were known only for fair disagreement minimization in complete unweighted graphs. We prove the following: (1) there is no finite approximation for fair disagreement minimization in general graphs unless P = NP (this hardness holds also for bicriteria algorithms); and (2) fair agreement maximization in general graphs admits a bicriteria approximation of ≈ 0.591 (an improved ≈ 0.609 true approximation is given for the special case of two uniformly distributed colors). Our algorithm is based on proving that the sticky Brownian motion rounding of [Abbasi ZadehBansalGuruganeshNikolovSchwartzSingh SODA'20] copes well with uncut edges.
BibTeX  Entry
@InProceedings{schwartz_et_al:LIPIcs.APPROX/RANDOM.2022.37,
author = {Schwartz, Roy and Zats, Roded},
title = {{Fair Correlation Clustering in General Graphs}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)},
pages = {37:137:19},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772495},
ISSN = {18688969},
year = {2022},
volume = {245},
editor = {Chakrabarti, Amit and Swamy, Chaitanya},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/17159},
URN = {urn:nbn:de:0030drops171591},
doi = {10.4230/LIPIcs.APPROX/RANDOM.2022.37},
annote = {Keywords: Correlation Clustering, Approximation Algorithms, SemiDefinite Programming}
}
Keywords: 

Correlation Clustering, Approximation Algorithms, SemiDefinite Programming 
Collection: 

Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022) 
Issue Date: 

2022 
Date of publication: 

15.09.2022 