<p>The statement of Ahuja, Magnanti, and Orlin applies to general flows, not only <span class="math-container">$(s,t)$</span>-flows. During decomposition, when removing a path flow, either one of the two endpoints become balanced or one the arcs will get flow 0. This gives the bound <span class="math-container">$m+n$</span>.</p>
<p>In the case of <span class="math-container">$(s,t)$</span>-flows, we may note that during decomposition the nodes <span class="math-container">$s$</span> and <span class="math-container">$t$</span> becomes balanced at the same time. This gives the already the bound <span class="math-container">$m+1$</span> on the number of paths and cycles. If we look at the flow decomposition, when finding the final path flow (this is where the balance of <span class="math-container">$s$</span> and <span class="math-container">$t$</span> becomes balanced), if no flow on some arc is made 0, it means that we will still find a cycle flow. Now the final cycle flow will make at least two arcs have flow 0 at the same time. This sharpens the bound to <span class="math-container">$m$</span> in case of <span class="math-container">$(s,t)$</span>-flows.</p>
<p>P.S. The proofs of the notes you link are not quite correct, see the comments.</p>

CC BY-SA 4.0
2021-02-22T08:36:17.770Z
Thank you very much, in my head, I was only thinking of (s,t)-flows with a single source and sink and not realizing the more general flow case. Now, if I understand it correctly, for general flows, the m+n bound can actually be tightened by defining n' to be the number of excess and deficit nodes. Then, as the final path must balance exactly two nodes, one deficit and one excess, the tighter bound is m+n'-1. (And with the cycle argument after the final path flow m+n'-2?)
saper0
CC BY-SA 4.0
2021-02-22T09:50:15.547Z
Yes, that seems correct.
Kristoffer Arnsfelt Hansen
CC BY-SA 4.0
2021-02-21T10:58:16.203Z
2021-02-21T11:15:23.613Z
2021-02-21T11:15:23.613Z
Kristoffer Arnsfelt Hansen
<p>In the classic <a href="https://mitmgmtfaculty.mit.edu/jorlin/network-flows/" rel="nofollow noreferrer">Network Flows: Theory, Algorithms, and Applications</a> book (pages 80/81) the flow decomposition theorem is stated as follows:</p>
<blockquote>
<p>Every nonnegative arc flow x can be represented as a path and cycle flow (though not necessarily uniquely) with the following two properties: <br />
(a) Every directed path with positive flow connects a deficit node to an excess node <br />
(b) At most n+m paths and cycles have nonzero flow; out of these at most m cycles have nonzero flow with m the number of edges and n the number of nodes in the graph</p>
</blockquote>
<p>My question is, if the theorem can be formulated more strongly modifying point b as follows:</p>
<blockquote>
<p>(b) At most m paths and cycles have nonzero flow</p>
</blockquote>
<p>My question arises as going through the lecture nodes of a more modern optimization course at Stanford, I find the flow decomposition theorem formulated exactly with this &quot;stronger&quot; assertion (page 58 with proof <a href="http://theory.stanford.edu/%7Etrevisan/cs261/all-notes-2010.pdf" rel="nofollow noreferrer">here</a> or a similar theorem <a href="http://theory.stanford.edu/%7Etrevisan/cs261/lecture11.pdf" rel="nofollow noreferrer">here</a>).</p>
<p>Going through the proofs in the lecture nodes and the book, I find the stronger formulation justified. Especially in <a href="https://mitmgmtfaculty.mit.edu/jorlin/network-flows/" rel="nofollow noreferrer">Network Flows: Theory, Algorithms, and Applications</a> the following argument is given for their m+n bound on paths:</p>
<blockquote>
<p>Now observe that each time we identify a directed path, we reduce the excess/deficit of some node to zero or the flow on some arc to zero;</p>
</blockquote>
<p>As I understand it, reducing the excess/deficit of some node to zero implies setting the flow on some arc to zero, as the excess/deficit flow of a node has to go/come over an arc whose flow is now set to zero. This however would imply bounding the number of paths with m instead of n+m, as each construction of a flow-path would remove one edge and not one edge or node from the graph.</p>
<p>Have I misunderstood the proof and are the lecture nodes from Stanford wrong? Do you know other books which one could possible cite for the stronger version of the flow decomposition theorem?</p>
<p>Thank you!</p>
<p>Note: In <a href="https://cstheory.stackexchange.com/questions/16606/can-a-flow-be-decomposed-in-a-given-number-of-paths?rq=1">this</a> question with the very promising title, a different question has been asked. It took the theorem from one of the aforementioned Stanford notes, and in the answers the correctness of it was discussed albeit for different reasons.</p>

CC BY-SA 4.0
2021-02-21T10:38:35.767Z
The proof in Plotkin's notes you link to is actually not quite correct. When we find an (s,t) path we are not allowed to subtract the path-flow with the minimum of the flow on the path. We would also need to take the minimum with the balance of s and the negative balance of t. (Trevisan's notes have the same issue).
Kristoffer Arnsfelt Hansen
CC BY-SA 4.0
2021-02-21T10:40:43.250Z
The quoted argument of Ahuja, Magnanti, and Orlin is the correct way to argue.
Kristoffer Arnsfelt Hansen
CC BY-SA 4.0
2021-02-21T10:44:44.347Z
Reducing excess/deficit of some node to zero implies that the node becomes balanced.
Kristoffer Arnsfelt Hansen
CC BY-SA 4.0
2021-02-21T22:37:48.890Z
Typically one works with s-t flows at the start with no explicit demand/supply. It is easy to reduce the general case with multiple sources and sinks with demands/supplies to s-t flow by adding new source, sink. Adding new source/sink creates at most n new edges so that is another way to think about the problem.
Chandra Chekuri
CC BY-SA 4.0
2021-02-22T09:46:48.270Z
And one may go all the way to a circulation by adding an arc from t to s.
Kristoffer Arnsfelt Hansen
<graph-theory><graph-algorithms><network-modeling><flow-problems>
A stronger Flow Decomposition Theorem?
saper0
# A stronger Flow Decomposition Theorem?

(Asked by: username_0 on 2021-02-18)

In the classic [Network Flows: Theory, Algorithms, and Applications](https://mitmgmtfaculty.mit.edu/jorlin/network-flows/) book (pages 80/81) the flow decomposition theorem is stated as follows:

> Every nonnegative arc flow x can be represented as a path and cycle flow (though not necessarily uniquely) with the following two properties:   
> (a) Every directed path with positive flow connects a deficit node to an excess node   
> (b) At most n+m paths and cycles have nonzero flow; out of these at most m cycles have nonzero flow with m the number of edges and n the number of nodes in the graph

My question is, if the theorem can be formulated more strongly modifying point b as follows:

> (b) At most m paths and cycles have nonzero flow

My question arises as going through the lecture nodes of a more modern optimization course at Stanford, I find the flow decomposition theorem formulated exactly with this "stronger" assertion (page 58 with proof [here](http://theory.stanford.edu/%7Etrevisan/cs261/all-notes-2010.pdf) or a similar theorem [here](http://theory.stanford.edu/%7Etrevisan/cs261/lecture11.pdf)).

Going through the proofs in the lecture nodes and the book, I find the stronger formulation justified. Especially in [Network Flows: Theory, Algorithms, and Applications](https://mitmgmtfaculty.mit.edu/jorlin/network-flows/) the following argument is given for their m+n bound on paths:

> Now observe that each time we identify a directed path, we reduce the excess/deficit of some node to zero or the flow on some arc to zero;

As I understand it, reducing the excess/deficit of some node to zero implies setting the flow on some arc to zero, as the excess/deficit flow of a node has to go/come over an arc whose flow is now set to zero. This however would imply bounding the number of paths with m instead of n+m, as each construction of a flow-path would remove one edge and not one edge or node from the graph.

Have I misunderstood the proof and are the lecture nodes from Stanford wrong? Do you know other books which one could possible cite for the stronger version of the flow decomposition theorem?

Thank you!

Note: In [this](https://cstheory.stackexchange.com/questions/16606/can-a-flow-be-decomposed-in-a-given-number-of-paths?rq=1) question with the very promising title, a different question has been asked. It took the theorem from one of the aforementioned Stanford notes, and in the answers the correctness of it was discussed albeit for different reasons.

**Tags:** graph-theory, graph-algorithms, network-modeling, flow-problems
> **Comments:**
> **username_1**: The proof in Plotkin's notes you link to is actually not quite correct. When we find an (s,t) path we are not allowed to subtract the path-flow with the minimum of the flow on the path. We would also need to take the minimum with the balance of s and the negative balance of t. (Trevisan's notes have the same issue).  
> **username_1**: The quoted argument of Ahuja, Magnanti, and Orlin is the correct way to argue.  
> **username_1**: Reducing excess/deficit of some node to zero implies that the node becomes balanced.  
> **username_2**: Typically one works with s-t flows at the start with no explicit demand/supply. It is easy to reduce the general case with multiple sources and sinks with demands/supplies to s-t flow by adding new source, sink. Adding new source/sink creates at most n new edges so that is another way to think about the problem.  
> **username_1**: And one may go all the way to a circulation by adding an arc from t to s.  

---

## 1 answers

### Answer by username_1 on 2021-02-21. Score: 3 | Accepted answer

The statement of Ahuja, Magnanti, and Orlin applies to general flows, not only $(s,t)$-flows. During decomposition, when removing a path flow, either one of the two endpoints become balanced or one the arcs will get flow 0. This gives the bound $m+n$.

In the case of $(s,t)$-flows, we may note that during decomposition the nodes $s$ and $t$ becomes balanced at the same time. This gives the already the bound $m+1$ on the number of paths and cycles. If we look at the flow decomposition, when finding the final path flow (this is where the balance of $s$ and $t$ becomes balanced), if no flow on some arc is made 0, it means that we will still find a cycle flow. Now the final cycle flow will make at least two arcs have flow 0 at the same time. This sharpens the bound to $m$ in case of $(s,t)$-flows.

P.S. The proofs of the notes you link are not quite correct, see the comments.

> **Comments:**
> **username_0**: Thank you very much, in my head, I was only thinking of (s,t)-flows with a single source and sink and not realizing the more general flow case. Now, if I understand it correctly, for general flows, the m+n bound can actually be tightened by defining n' to be the number of excess and deficit nodes. Then, as the final path must balance exactly two nodes, one deficit and one excess, the tighter bound is m+n'-1. (And with the cycle argument after the final path flow m+n'-2?)  
> **username_1**: Yes, that seems correct.  

---

