<p>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.</p>

<p>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.</p>

CC BY-SA 3.0
2014-10-14T11:07:43.440Z
2014-10-14T11:07:43.440Z
Mathijs
<p>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)? </p>

<p>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$. </p>

<p>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$ .</p>

<p>Is my intuition correct or not?</p>

<np-complete><max-flow><max-flow-min-cut>
Flow networks: Push flow on either edges but not both!
Adel Ali
# Flow networks: Push flow on either edges but not both!

(Asked by: username_0 on 2014-10-14)

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?

**Tags:** np-complete, max-flow, max-flow-min-cut

---

## 1 answers

### Answer by username_1 on 2014-10-14. Score: 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.


---

