Maximum Flow with recursive, dynamic weights

Question

I am looking for an algorithm that functions similarly to the maximum flow algorithm. The only difference is that each edges weight changes according to the weight that it was traversed before, and the edge capacities are defined by the total flow achieved at the sink t. Are there any algorithms that cover these cases? Or is there any unrolling methods I can look into?

Answer 1

In general, the problem is intractable. It is easy to show that it is NP-hard. Suppose that there is a single edge into t. Suppose that you specify that the capacity on this edge depends on the edges that were previously traversed as follows: it is equal to the number of edges previously traversed by the flow. Suppose that all other edge capacities are $+\infty$. Then the solution to your problem will be the same as the longest path in the graph. It is known that finding the longest path is NP-hard (by reduction from the Hamiltonian path problem), so your problem is NP-hard as well, in general.

In fact, it is impossible to even represent the input (to specify an arbitrary dependence) in a reasonable amount of space; it takes exponential space to represent a general dependence of the edge capacity on all the edges that were traversed previously.