Suppose I were given some mapping f on a flow network represented as a sparse matrix of flows on each edge. Would it be possible to verify that this mapping is indeed a flow in polynomial time?

i.e. it would need to satisfy

1. Every edge in the flow network is assigned a positive number less than the capacity
2. The edges going into a node equal the edges leaving the node

If I were to do a BFS on this flow network, I am worried I could run into the issue where for every edge in the DAG I would need to iterate over every one of the outgoing edges and I am unsure if this will take exponential time or not. Would this be possible to do in polynomial time?

CodePudding user response：

I think you can do it in O(V E) time :

1. For every vertice v make a counter counter_v at 0.

2. For every edge e, check that f(e)<= c(e) (the flow is less than the capacity). If that's not the case, you're done, it's not a valid flow. Else, with e going from v1 -> v2 you decrement v1's counter by the flow, and increment v2's by the flow : counter_v1 -= f(e); counter_v2 = f(e)

3. For every vertice other than s and t, check that the counter is 0, ie the total flow going through the vertice is 0.

That's it, you checked every vertice twice and every edge once, so O(V E)