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 union 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.
This is joint work with Philip Klein and Claire Mathieu.