<p>I wrote an algorithem that solve a bipartite with a lot of constrains and this was one of them. but to solve it i did not use a residual graph, and the solution is not very effective, but it's working good enough for my goals. I used capacity scalling algorithem and i disabled all the residual edges so the flow only push forward (without the ability to undo). and to compensate on cases in which the flow is not the maximum possible flow. i run this algorithem couple of times, each time suffeling the nodes in the graph. at the end i have choosen the solver that had the maximum flow. not sure about how good it solve non bipartite problem or a large one.</p>

CC BY-SA 4.0
2024-05-11T05:20:10.593Z
2024-05-11T05:20:10.593Z
NIl Hart
<p>This problem is NP-hard.</p>

<p>Reduction from <em>PARTITION</em>:</p>

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

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

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

CC BY-SA 3.0
2014-09-19T21:51:50.287Z
2014-09-24T22:37:31.570Z
2014-09-24T22:37:31.570Z
R B
<p>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.</p>

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

<graph-algorithms><time-complexity><max-cut><max-flow>
Max flow: either saturate an edge or avoids
Quanquan Liu
# Max flow: either saturate an edge or avoids

(Asked by: username_0 on 2014-09-19)

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?

**Tags:** graph-algorithms, time-complexity, max-cut, max-flow


---

## 2 answers

### Answer by username_2 on 2014-09-19. Score: 9 | Accepted answer

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


---

### Answer by username_1 on 2024-05-11. Score: -1

I wrote an algorithem that solve a bipartite with a lot of constrains and this was one of them. but to solve it i did not use a residual graph, and the solution is not very effective, but it's working good enough for my goals. I used capacity scalling algorithem and i disabled all the residual edges so the flow only push forward (without the ability to undo). and to compensate on cases in which the flow is not the maximum possible flow. i run this algorithem couple of times, each time suffeling the nodes in the graph. at the end i have choosen the solver that had the maximum flow. not sure about how good it solve non bipartite problem or a large one.


---

