Min Power Strong Connectivity

• INSTANCE: Directed graph $G=(V,E)$ , cost function $c: E \rightarrow R_+$
• SOLUTION: Strongly connected spanning subgraph $H$ of $G$
• COST FUNCTION: $p(H)=\sum_{u\in V}p_H(u)$ , where $p_H(u)=\max\{c(u,v)\vert(u,v)\in H\}$
• OBJECTIVE: Minimize

• Approx.: Approximable within approximation ratio $2$ . Approximable within approximation ratio 1.85 provided $G$ is bidirected [23].