I have that problem in my mind and cannot figure out how to solve it, the problem as follow:
Given n clients (1 - n) , m shops and every shop can serve a set of clients (this set is given in the input), so maybe the client can be served by more than one shop, what is the minimum number of shops that can cover(serve) all clients?
I thought about max flow but I failed to come up with the solution.. I know that min cost algorithm will pay for every flow a specific cost, could I modify the algorithm so every X flow will pay only (1) cost?
Any ideas?
I was thinking on this problem just about 30mins ago...
I'm interested about the answer too...
Each shop can only serve a given subset of the clients, or it can serve any clients?
I think each shop will serve a given subset and you don't have to choose just one of the clients for a shop, it can serve all of the clients at once...
Actually we have a bipartite graph and we want to choose minimum number of vertices from part A such that each vertex in part B would be adjacent to at least one of the chosen vertices...(If I understood his problem correctly)
Edited!
Auto comment: topic has been updated by Mhammad1 (previous revision, new revision, compare).
Isn't it NP-hard?
If I understood your problem correctly, it is the same as the Set cover problem. It is NP-complete.
Actually yes you're correct, the problem is NP-complete, thanks for your help :D
But one more thing, can I modify the min-cost algorithm to pay
(1)cost for each(X)flow?isn't this a special case of set cover but not exactly set cover so this might be solvable right
How is it a special case?
A variation of Algorithm X will do this for you — just keep the columns of the matrix untouched when processing/backtracking guesses. The DLX implementation can solve this quite efficiently despite its NPC nature.
Algorithm X find any solution but not the minimum solution .
if n is less than 20 you can solve it with dp+bitmask