1
$\begingroup$

I'm working with a flow network like the following:

The source s has four edges, each with capacity 1, out to the nodes A, B, C, and D. All of A, B, C, and D have edges to two other nodes, X and Y, also with capacity 1. X and Y both have edges with capacity 4 to the sink t.

Typically this would have many solutions: all of the ways you could split up A, B, C, and D between X and Y. In the modified version, I have to pick either X or Y. If the flow on (X, t) > 0, the flow on (Y, t) must be 0, and vice versa. So there are only two solutions, sending all 4 units of flow through X or through Y.

I'm wondering if there is a way to reduce this constraint to the standard max-flow so I can just run Ford-Fulkerson on a modified graph. That, or whether this is fundamentally harder and is an isomorphism of a different problem.

In simpler versions like the one I've laid out above you could just reduce the decision to a problem where you have only s, t, and the nodes X and Y and must send 1 unit of flow through the network, but I'm struggling with the general case where we have two edges X and Y, only one of which is allowed to have nonzero flow through it in the solution.

$\endgroup$
3
$\begingroup$

You can reduce SAT to this version. Connect the source to nodes $x_1,\ldots,x_n$, one per variable, with infinite capacity. Connect each $x_i$ to two exclusive nodes $x_i^T,x_i^F$, with infinite capacity. Create one node per clause, and connect a literal to a clause (with infinite capacity) if the clause contains the literal. Finally, connect each clause to the sink with unit capacity. The maximum flow is the number of clauses iff the formula is satisfiable.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.