# Find a max flow in a flow network that passes through a fixed number of nodes

I want to solve a network flow problem with the usual setup of a directed graph with a capacity value for each edge. However, I also have an additional constraint: I want to find the maximum flow through any subset of size K of the vertices of the network.

Informally, I think there's not going to be a polynomial time solution to this problem because given a solution, merely verifying that the flow is maximal among all possible sets of nodes of size K is hard.

Any thoughts?

Thanks!

• Can you clarify your question a bit? (1) Given k do you want to find the subset of vertices of size k that has the most flow going through them or (2) Given a fixed subset of size k, you want to reroute the max flow to have as much flow as possible through these k vertices? – Sandeep Silwal Dec 3 '18 at 15:45