License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2022.37
URN: urn:nbn:de:0030-drops-171591
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/17159/
Go to the corresponding LIPIcs Volume Portal

Schwartz, Roy ; Zats, Roded

Fair Correlation Clustering in General Graphs

pdf-format:
LIPIcs-APPROX37.pdf (0.8 MB)

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 Zadeh-Bansal-Guruganesh-Nikolov-Schwartz-Singh 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:1--37:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-249-5},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{245},
  editor =	{Chakrabarti, Amit and Swamy, Chaitanya},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2022/17159},
  URN =		{urn:nbn:de:0030-drops-171591},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2022.37},
  annote =	{Keywords: Correlation Clustering, Approximation Algorithms, Semi-Definite Programming}
}

Keywords: Correlation Clustering, Approximation Algorithms, Semi-Definite Programming
Collection: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)
Issue Date: 2022
Date of publication: 15.09.2022

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI