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.

| cite | improve this question | | | | |
  • 1
    $\begingroup$ 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. $\endgroup$ – Dean Gurvitz Oct 27 '18 at 8:12
  • $\begingroup$ 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. $\endgroup$ – Jonathan Oct 27 '18 at 8:15
  • 1
    $\begingroup$ 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. $\endgroup$ – Dean Gurvitz Oct 27 '18 at 8:22

The question clearly states that the capacities apply to cities, not railway lines. Cities are vertices in the graph, not edges.

| cite | improve this answer | | | | |
  • $\begingroup$ Then how can I transform this to a maxflow problem when the capacities are the cities? $\endgroup$ – Jonathan Oct 27 '18 at 14:24
  • $\begingroup$ Your answer for edges was almost right... $\endgroup$ – David Richerby Oct 27 '18 at 14:25
  • $\begingroup$ Would I need to do something like this? en.wikipedia.org/wiki/… $\endgroup$ – Jonathan Oct 27 '18 at 14:31
  • $\begingroup$ 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). $\endgroup$ – David Richerby Oct 27 '18 at 14:34
  • $\begingroup$ Ok so could I do something like make all edges that lead to some V in be +infinity? $\endgroup$ – Jonathan Oct 27 '18 at 14:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.