# Maxflow problem

I need help with the following practice problem on network flow:

A cohort of $$k$$ spies resident in a certain country needs escape routes in case of emergency. They will be travelling using the railway system which we can think of as a directed graph $$G = (V, E)$$ with $$V$$ being the cities. Each spy $$i$$ has a starting point $$s_i\in V$$ and needs to reach the consulate of a friendly nation; these consulates are in a known set of cities $$T\subseteq V$$. In order to move undetected, the spies agree that at most $$c$$ of them should ever pass through any one city. Our goal is to find a set of paths for each of the spies (or detect that the requirements cannot be met). Model this problem as a flow network. Specify the vertices, edges and capacities, and show that a maximum flow in your network can be transformed into an optimal solution for the original problem. You do not need to explain how to solve the max-flow instance itself.

My thought was to make all edge weights have capacity $$c$$. Then, just use Ford-Fulkerson to find paths in the residual graph. But I'm not sure if this is the right approach because maybe we will have more than $$c$$ go through a node.

• Welcome to the site. This seems like a HW question. It is usually recommended to specify that explicitly if that's the case. In addition, you're much more likely to get help if you say how you tried solving the question yourself, and where you got stuck, or at least provide more context. – Dean Gurvitz Oct 27 '18 at 8:12
• No problem. So it is a practice problem and the thought that I had to approach it was to make all edge weights have capacity c. Then just use ford-fulkerson to find paths in the residual graph. But I'm not sure if this is the right approach because maybe we will have more than c go through a node. – Jonathan Oct 27 '18 at 8:15
• I used details from your comment to edit your question. Next time you can also use the quote ">" to separate the exercise from the rest of the question, and Mathjax to format equations and mathematical symbols. – Dean Gurvitz Oct 27 '18 at 8:22

• Yes, that will do the job. The edges representing cities will have weight $c$, and you need to ensure that the other edges have weight high enough to allow any number of spies to travel on them (because they've only agreed to restrict how many of them visit any particular city). – David Richerby Oct 27 '18 at 14:34