A polylogarithmic approximation algorithm for 2-edge-connected dominating set

In the CONNECTED DOMINATING SET (CDS) problem we are given a graph G and seek a min-size dominating set S such that the subgraph G[S] of G induced by S is connected. In the 2-EDGE-CONNECTED DOMINATING SET problem G[S] should be 2-edge-connected. We give the first non-trivial approximation algorithm for this problem, with expected approximation ratio O(log²⁡n⋅log⁡log⁡n⋅(log⁡log⁡log⁡n)³). We also show that the SUBSET STEINER CDS problem is approximation equivalent to the GROUP STEINER TREE problem.