摘要：In correlation clustering, the input is a graph with edge-weights, where every edge is labelled either + or - according to similarity of its endpoints. The goal is to produce a partition of the vertices that disagrees with the edge labels as little as possible. In two-edge-connected augmentation, the input is a graph with edge-weights and a subset R of edges of the graph. The goal is to produce a minimum weight subset S of edges of the graph, such that for every edge in R, its endpoints are two-edge-connected in R\cup S. For planar graphs, we prove that correlation clustering reduces to two-edge-connected augmentation, and that both problems have a polynomial-time approximation scheme.
