The VPN problems with concave costs