Maximum flow problem with flow into two non-adjacent nodes either be simultaneously greater than 0 or all 0s I have a directed graph that I want to find a maximum flow. But there are two non-adjacent nodes, say $a$ and $b$, that I want either the flows coming into $a$ and $b$ are simultaneously greater than $0$, or simultaneously $0$. I know max flow algorithm can be extended to edge disjoint, node disjoint and edge demand problems, but the kind of constraint I described above does not seem to have a solution. I tried to add an extra node, say $c$, and then add edges from $a$ to $c$, $b$ to $c$, and $c$ to the sink $t$, and then converted it to some sort of the mentioned extensions, but it seems hopeless.
Edit: directed graph, the flow can be integers, but it is not required.
 A: With such constraints it is possible that there is no maximum flow, but instead an upper limit that can be approached but not reached exactly. Consider  for example:
              *-------*Sink
             / \     /
        *   /   b   /
       / \ /     \ /
Source*---a-------*

where every edge goes from left to right and has a capacity of $1$.
You can't have any flow at all unless something flows into $a$, so there must be some flow through the diagonal that has $b$ on it. But the total flow you can get is exactly $2$ minus that diagonal flow, so you can approach a flow of $2$ by choosing the flow through $b$ as small as you want, as long as it is positive.
The magnitude of this limiting flow is easy enough to find, though:


*

*First remove both $a$ and $b$ from the graph and find a maximum flow through what is left. This fallback solution will certainly satisfy your condition.

*Now find a new maximum flow through the entire graph, ignoring your additional condition. Call the result the "optimistic" solution.

*If the optimistic solution either satisfies your condition or it is no better than the fallback solution, then we're done: either way we know a maximal flow that satisfies your condition.

*Otherwise, suppose without loss of generality that $a$ has flow in the optimistic solution but $b$ hasn't.

*Construct the residual network (like in the Ford-Fulkerson method) corresponding to the optimistic solution. See if it contains any cycle that includes $b$. If it does, you can add half of that cycle to the optimistic solution, and get one with the same total flow, but positive flow into both $a$ and $b$.

*Otherwise, check there is any path from the source to $b$ to the sink. If not, no flow through $b$ is possible, so go back to the fallback solution instead.

*Otherwise, we can at least approach the flow from the optimistic solution arbitarily well. Namely: Multiply all flows by $1-\varepsilon$ for some sufficiently small $\varepsilon$. Now all edges are in play again, and you can add a small "tickle flow" through $b$ to make it meet your condition.


If you require that flows are integers, the approximation won't work, of course. Instead, if $a$ has a total flow of $1$ in the optimistic solution, the search for a correction in step (5) needs to be modified to avoid taking that flow away. This is probably easiest to do by splitting $a$ into an input and an output node, with an edge between them whose back-edge you omit from the residual network. (And if you then don't find a solution, then the fallback solution is in fact best possible).
