# Use the maximum-flow, minimum-cut theorem and the Ford-Fulkerson algorithm

Consider a city with m parallel horizontal streets and n parallel vertical avenues. These lines cross in m × n intersections. On k ∈ {1, . . . , m × n} of these intersections, special checkpoints are placed. We want to place video cameras on a subset of the streets and of the avenues such that each checkpoint is in the visibility range of a camera. A camera allows to monitor all the checkpoints of an avenue or of a street. The subset of may contain both horizontal streets and vertical avenues. Clearly, you can always select all m + n of these streets and avenues. The challenge therefore is to select a smallest subset of these streets and avenues such that each checkpoint is in the visibility range of a camera.

Problem: Give an algorithm that finds such a smallest subset of streets and avenues where to place cameras in time polynomial in m and n. Prove that the algorithm is correct and provide an analysis of its running time.

• What have you tried? Where did you get stuck? – dkaeae Dec 6 at 14:07
• Welcome to Computer Science! We discourage posts that simply state a problem out of context, and expect the community to solve it. Assuming you tried to solve it yourself and got stuck, it may be helpful if you wrote your thoughts and what you could not figure out. It will definitely draw more answers to your post. Until then, the question will be voted to be closed / downvoted. You may also want to check out these hints, or use the search engine of this site to find similar questions that were already answered. – Apass.Jack Dec 6 at 14:46