Local Guarantees in Graph Cuts and Clustering

Correlation Clustering is an elegant model that captures fundamental graph cut problems such as Min s-t Cut, Multiway Cut, and Multicut, extensively studied in combinatorial optimization. Here, we are given a graph with edges labeled + or - and the goal is to produce a clustering that agrees with the labels as much as possible: + edges within clusters and - edges across clusters. The classical approach towards Correlation Clustering (and other graph cut problems) is to optimize a global objective. We depart from this and study local objectives: minimizing the maximum number of disagreements for edges incident on a single node, and the analogous max min agreements objective. This naturally gives rise to a family of basic min-max graph cut problems. A prototypical representative is Min Max s-t Cut: find an s-t cut minimizing the largest number of cut edges incident on any node. We present the following results: (1) an O(√n)-approximation for the problem of minimizing the maximum total weight of disagreement edges incident on any node (thus providing the first known approximation for the above family of min-max graph cut problems), (2) a remarkably simple 7-approximation for minimizing local disagreements in complete graphs (improving upon the previous best known approximation of 48), and (3) a 1/(2+varepsilon)-approximation for maximizing the minimum total weight of agreement edges incident on any node, hence improving upon the 1/(4+varepsilon)-approximation that follows from the study of approximate pure Nash equilibria in cut and party affiliation games.