2
$\begingroup$

Is there a way to create a max flow graph such that it satisfies the condition that a flow either saturates an edge or completely avoids it. It can't have half its flow through one edge and half through another edge.

Can this be formulated as a max flow problem with a polynomial time solution or is this problem hard?

$\endgroup$
9
$\begingroup$

This problem is NP-hard.

Reduction from PARTITION:

Given a set of numbers $S=\{x_1,\ldots,x_n\}$, construct the following flow network:

$$V = \{s,v,t\}\cup \{x_1,\ldots,x_n\}$$ $$E = \{(s,x_i) | x_i\in S\} \cup \{(x_i,v)|x_i\in S\} \cup \{(v,t)\}$$ $$c((s,x_i))=c((x_i,v))=x_i\ \ \ c((v,t))=\frac{\sum_{i\in[n]}{x_i}}{2}$$

$S$ is partitionable iff there exist "saturate edge or avoid" flow of value $c((v,t))$.

$\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.