VPN feasible solution

In contrast, we focus locally on the capacity installed on an edge, and weshow that, given any feasible solution, we can obtain a new solution with acapacitated central hub node, such that, on average the capacity on an edgeis at most doubled. This result is independent on the cost function. Still, wereinterpret the known fact that, given a set of paths, the minimal amount ofcapacity to install on an edge can be computed by solving a bipartite matchingproblem on some auxiliary graph. Using duality, we look instead at minimalvertex covers on such graphs, and this reinterpretation allows us to develop avery simple analysis for our statement.Eventually, we answer the open question regarding the complexity status ofthe balanced Vpn problem with linear costs. We prove that it is NP-hard evenwith unit thresholds on each node. In this section we describe in detail the problem addressed in this paper, andother related problems that we will use to state our results.(Concave/Linear) Virtual Private Network. An instance I of the concaveVirtual Private Network (cVpn) problem consists of an undirected connectedgraph G = (V, E) with edge costs c : E → Q+, two non-negative integer vectorsb+∈ ZV, b−∈ ZV, as well as a concave non-decreasing function f : Q+ → Q+.A vertex v such that b+v + b−v > 0 is referred to as a terminal: by duplicatingnodes, we can assume without loss of generality that each terminal is either asender s, with b+s > 0, b−s = 0, or a receiver r, with b+r = 0, b−r > 0. Let S andR be set of senders and receivers, respectively.