An interesting graph problem

Revision en1, by notking, 2018-05-12 18:56:49

Given a graph with n nodes and at most n^2 edges.

Each vertex contains some people residing in it initially.

Each vertex has a capacity to withstand total number of people who have visited it the whole time. When people go from a vertex A to B (they need not travel in groups) you can suppose that they have visited A and not B (the capacity of B doesn't decrease).
This means if there are 8 people on vertex x and it has capacity of 4 then no more than 4 people can go from vertex x to anywhere else. How many vertices are such that all people can visit it without breaking the constraints above?

I am looking for something better or around O(N^4).

Tags graph, flow, capacity

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English notking 2018-05-12 18:56:49 691 Initial revision (published)