We study a problem in the area of robust network design; here we are interested in setting up a network to facilitate uncertain or time varying communication patterns between some set of terminals. In this talk I will discuss the masked VPN problem, in which this uncertainty is modelled by allowing any communication pattern satisfying a set of prespecified bounds, consisting of individual bounds on the communication coming from any terminal, as well as pairwise bounds imposed on the communication flowing between terminals. This model is very natural when considering, for example, digital networks.

Using the duality between the maximum matching and minimum vertex cover problems, we can derive an interesting alternative interpretation of the problem, in which terminals must buy overlapping connections in the graph. From here the connection to well-studied network design problems such as the Steiner tree problem (and therefore the shortest path problem) is easily made. In the rest of the talk I will go over some of our results on the structure of optimal solutions to the masked VPN problem. Joint work with Neil Olver.