Total number of variables for a general maximum flow varaible

Question

Consider the maximum flow problem with n nodes and m arcs. You are writing a formulation with f as the maximum flow. The total number of variables is _____ ?

I have been asked this question for a homework as part of operations research course. I thought the answer as m as there are m arcs. But the answer is given as m+1 where the extra 1 is by considering f as a variable. I couldnt understand how number of variables could exceed m as f includes some arcs of f.

EDIT: There is single source and sink

Answer 1

Is this a traditional max flow problem (in which there is a single source node, a single sink node, and you are supposed to maximize the combined flow from source to sink across all routes)? If so, I suspect the extra variable $f$ is the value of the objective function. Suppose that we let $x_a$ denote the flow across a given arc $a$. You are correct that there will be $m$ of these flow variables. We can then write the total flow (objective value) as either the sum of the $x_a$ where arc $a$ terminates at the sink, or equivalently the sum of $x_a$ where $a$ originates at the source. Whichever one we use, we can plug that directly into the objective function or assign the value of the summation to a new variable $f$ and maximize $f$. I suspect that's what your instructor is doing.

Answer 2

You are absolutely right that the $m$ arcs will cause $m$ variables in the problem. Often, however, people include an additional $(m+1)$-th variable which indicates the flow from the sink back to the source. When they do so, they also add additional flow conservation constraints for the sink and the source. The original objective function can then be replaced by $\max x_{ts}$ where $x_{ts}$ is the additional variable of flow from source to sink. This is because $x_{ts} = \sum x_{sv}$ where the latter sum is the original objective function.

This procedure will yield a closed network. I assume that your textbook is following this approach. For more information about this approach with some nice graphics for illustration see here, for example.