A network flow with different constraints

2
votes

Considering a simple network flow model: G = (V,E), source node S, and sink node T. For each edge E[i], its capacity is C[i].

Then the flow F[i] on edge E[i] is constrained to be either C[i] or 0, that is, F[i] belongs to {0, C[i]}.

How to compute the maximum flow from S to T? Is this still a network flow problem?

2
algorithmgraph-algorithm
Same as the general algorithm. It will be the flow of the minimum cut. Your constraint doesnt change much. btw belongs on cs.stackexchange.com - UmNyobe
@UmNyobe are you sure? Let's consider a trivial graph with nodes {S, M, T} and edges {E1 = (S, M), E2 = (M, T)} with C(E1) = 1 and C(E2) = 2. It seems to me that the max flow under the stated constraints is 0, which is definitely not the minimum cut. - Vincent van der Weele
The modified problem looks NP hard - Niklas B.

2 Answers

1
votes

The decision variant of your modified flow problem is NP-complete, as evidenced by the fact that the subset sum problem can be reduced to it: For given items w_1, ..., w_n and a sum W, just create a source S connected to every item i via an edge S -> i of capacity w_i. Then connect every item i to a sink t via another edge i -> t of capacity w_i. Add an edge t -> T of capacity W. There exists a subset of items with cumulative weight W iif the S-T max-flow in the graph is W with your modifications.

That said, there is likely no algorithm that solves this problem efficiently in every case, but for instances not specifically designed to be hard, you can try an integer linear program formulation of the problem and use a general ILP solver to find a solution.

There might be a pseudopolynomial algorithm if your capacities are integers bounded by a value polynomial in the input size.

0
votes

Um, no its no longer a well defined flow problem, for the reason that Heuster gives, which is that given two edges connected through a node (with no other connections) the flow must be zero unless the two capacities equal each other. Most generic flow algorithms will fail as they cannot sequentially increase the flow.

Given the extreme restrictivity of this condition on a general graph, I would fall back on a game tree working backwards from the sink. Most nodes of the game tree will terminate quickly as there will be no combination of flows into a node that exactly match the needed outflows. With a reasonable heuristic you can probably find a reasonable search order and terminate the tree without having to search every branch.

In fact, you can probably exclude lots of nodes and remove lots of edges before you start, on the grounds that flows through certain nodes will be trivially impossible.