- INSTANCE:
Directed graph
and a weight function
.
- SOLUTION:
A connectivity augmenting set
*A'*for*G*, i.e., a set*A'*of ordered pairs of vertices from*V*such that is strongly connected. - MEASURE:
The weight of the augmenting set, i.e.,
.

*Good News:*Approximable within 2 [172].*Comment:*The unweighted problem (i.e. where all weights are 1) is approximable within 1.61 [317].*Garey and Johnson:*ND19