I have a flow network with random capacities on edges, is there some way to add a constraint of the type (push flow on either one of these two edges but not on both)?

I'm not sure if this is correct or not, but I think the maximum independent set problem can be reduced to the problem I stated above, let's call our graph $S$ and make a flow network $G$ with a source node $src$ and sink node $sink$.

For each vertex $v \in V(S)$ we make an edge $(src \rightarrow sink)$ with capacity 1 in $G$ and for each edge $(A \rightarrow B) \in E(S)$ we add the constraint to pass flow on either the edge that corresponds to $A$ or $B$ in $G$ . The resulting maximum flow on $G$ is the cardinality of the maximum independent set on $S$ and the set of saturated edges in $G$ are the nodes in the maximum independent set of $S$ .

Is my intuition correct or not?


1 Answer 1


You can model the constraint of not using two edges (u,v) and (u,w) of capacity one simultaneously in a flow network by introducing a vertex u' and an edge (u',u) with capacity one, but I'm not aware of a more general way to do this without extending the concept of a flow network.

If your idea for reducing the maximum independent set problem to a network flow problem worked, you'd have the basis for a proof that P=NP, which is extremely unlikely.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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