Graph with n people and k destinations

Question

In a connected graph, there are n points where hungry people are standing. Every hungry person wants to go one of the k restaurants in the graph. The travel distance should be within a 1 km distance for each person. A restaurant can fit no more than CEILING[n/k] guests.

Provided the points of these hungry people and the restaurants in the area, is there an efficient algorithm that runs in polynomial time that tells whether EVERY guest can be accommodated (as in True or False)?

This sort of reminds me of the Travelling Salesman problem so is it just a modified version of it?

Answer 1

This is an example of a matching problem on a bipartite graph. This is much easier to solve than the travelling salesman problem and can be done in O((n+k)^3).

There are two subproblems:

1. Find which people can reach each restaurant
2. Find how to match people to restaurants to avoid overflowing the constraints

Reaching Restaurants

It is possible to compute the shortest path between any pair of points in O(n^3) by using, for example, the Floyd-Warshall algorithm.

The allowed matchings are then the connections of distance less than 1 km.

Matching people to restaurants

This matching problem can be solved by constructing a graph and then solving for the maximum flow.

An appropriate graph is to have a source node, a sink node, and a node for each person and each restaurant.

1. Connect the source to each person with capacity 1
2. Connect each person to each restaurant within 1km with capacity 1
3. Connect each restaurant to the sink node with capacity Ceil(n/k).

Then compute the maximum flow through this graph. Every guest can be accomodated if and only if the maximum flow is n.

There are many algorithms to compute the maximum flow. One example would be push-relabel with complexity O(V^3) where V is the number of vertices (V=n+k+2 in this problem).