3
$\begingroup$

In the classic Network Flows: Theory, Algorithms, and Applications 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 or a similar theorem here).

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

$\endgroup$
5
  • 1
    $\begingroup$ 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). $\endgroup$ Feb 21, 2021 at 10:38
  • $\begingroup$ The quoted argument of Ahuja, Magnanti, and Orlin is the correct way to argue. $\endgroup$ Feb 21, 2021 at 10:40
  • $\begingroup$ Reducing excess/deficit of some node to zero implies that the node becomes balanced. $\endgroup$ Feb 21, 2021 at 10:44
  • 2
    $\begingroup$ 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. $\endgroup$ Feb 21, 2021 at 22:37
  • $\begingroup$ And one may go all the way to a circulation by adding an arc from t to s. $\endgroup$ Feb 22, 2021 at 9:46

1 Answer 1

3
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ 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?) $\endgroup$
    – saper0
    Feb 22, 2021 at 8:36
  • 1
    $\begingroup$ Yes, that seems correct. $\endgroup$ Feb 22, 2021 at 9:50

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.