Let $N=(V,E,s,t,c)$ be a network (defined as usual). The "Max-flow min-cut" theorem states that the max flow passing from the source $s$ to the sink $t$ is given by the minimal cut.
https://en.wikipedia.org/wiki/Max-flow_min-cut_theorem
Fix a subset $V_0\subset V$. We will say that a flow $f$ is $V_0$-symmetric if the following, property holds:
$$ f(v, v_1)=f(v,v_2) \ \ \ \ \ \forall v_1, v_2 \ \text{such that} \ (v,v_1), (v,v_2)\in E,$$ for all $v\in V_0$. In other words, the flow coming out of $v\in V_0$ is divided equally among all the edges coming out from $v$.
My question is rather naive:
can we somehow calculate the maximal $V_0$-symmetric flow through $N$?
can this problem be somehow reduced to the "Max-flow min-cut" theorem?
I will be glad for any ideas and comments.
This is known as a simple equal-flow. There is a paper by Ahuja, Orlin, Sechi and Zuddas that give several algorithms to solve it. In short, if you don't care about an integral solution, you are just adding one family of constraints to the linear program, so that does not make it much harder. If you want an integral solution, the best you can do is round either up or down the flow value on $V_0$ in the optimal solution, and then find a maximum flow with those values fixed. This is because the max flow parametrized by the flow value for the arcs at equality is convex.
When given several classes of equality constraints, this is the equal-flow problem. Again it is not hard to find an optimal fractional solution, using linear programming for instance, and it becomes NP-hard to find integral optimal solutions.
To derive a "min-cut" equivalent, we use the linear programming dual. Let's denote $E^=$ the set of arcs that we want to have equal flow. First we give a linear program for the simple equal-flow problem, using one variable $x_e$ representing the flow value on each arc $e \in E \setminus E^=$, and one variable $x_=$ representing the flow value on each arc in $E^=$. Let $c^=$ be the minimum capacity on an arc in $E^=$, and for any vertex $v \in V$, denote $d^=(v) = |\delta^-(v) \cap E^=| - |\delta^+(v) \cap E^=|$. We also use the trick of adding an arc from $t$ to $s$. The primal linear program, for the maximal flow, is then
$ \begin{equation} \max\;x_{ts}\;\textrm{s.t.} \\ \qquad x(\delta^-(v) \setminus E^=) - x(\delta^+(v) \setminus E^=) + d^=(v) x_= = 0 \qquad(\forall v \in V)\\ \qquad 0 \leq x_e \leq c_e \qquad(\forall e \in E \setminus E^=)\\ \qquad 0 \leq x_= \leq c^= \end{equation} $
From this, we can compute the dual program. We use variable $p_v$ for the dual variable attached to the primal constraint on vertex $v$, variable $y_e$ for the variable attached to the primal constraint $x_e \leq c_e$, and variable $y_=$ for the constraint $x_= \leq c^=$. This gives:
$\begin{equation} \min\;\sum_{e \in E \setminus E^=} y_e c_e + y_= c^=\;\textrm{s.t.}\\ \qquad y_{uv} \geq p_u - p_v \qquad(\forall e = uv \in E \setminus E^=)\\ \qquad p_s - p_t \geq 1\\ \qquad y^= \geq \sum_{uv \in E^=} p_u - p_v\\ \qquad y \geq 0 \end{equation} $
As in the analysis of the dual of max-flow, we can simplify this program in two ways. First $p$ is defined up to some additive constant, so we can force $p_t =0$. Second because the capacities are positive, the optimal solutions will take $y$ as small as possible, which is $y_{uv} = \max \{0, p_u - p_v\}$ and $y_= = \max \{ 0, \sum_{uv \in E^=} p_u - p_v\}$. This gives:
$\begin{equation} \min\;\sum_{e = uv \in E \setminus E^=} \max\{0,p_u-p_v\} c_{uv} + \max\{0,\sum_{uv \in E^=} p_u - p_v\} c^=\;\textrm{s.t.}\\ \qquad p_t = 0\\ \qquad p_s \geq 1 \end{equation}$
$p$ is the potential function on the vertices of the graph. The interpretation is that each unit of flow goes from $s$ to $t$, hence from potential $\geq 1$ to potential $0$, so must lose one unit of potential. So each arc will contribute to this loss of potential. We now simply bound how much potential can be lost in total, bounding the maximum possible flow. If an arc $uv$ is decreasing, then the best we can do is to send as much flow as possible, contributing $(p_u - p_v)c_{uv}$. Otherwise, the best we can do is not to send any flow, contributing $0$. Similarly for the arcs in $E^=$, there are only two possible strategies, send $c^=$ or $0$ flow on them, depending on how much the potential decreases in total over those arcs. Up to now this is working as in the classical max flow problem.
Now let $\{\pi_0, \pi_1, \ldots, \pi_k\} = \{p_v : v \in V\}$ with $\pi_0 > \pi_1 > \ldots \pi_k$ be the potential values in decreasing order. We can define a family of cuts $S_i = \{ v \in V : p_v \geq \pi_i\}$ for all $i \in \{1,\ldots,k\}$. In the classical flow problem, one can argue that all these cuts have equal capacities $c(\delta^+(S_i))$, and this gives max-flow min-cut. The idea is that we may change $p$ on $S_1 \setminus S_0$ by any $\epsilon$ with $|\epsilon|$ small enough, changing the objective value of the dual linearly, but by optimality this implies that actually the objective stays constant. From that we get that setting $p_u = \pi_0$ for all $u \in S_1 \setminus S_0$ does not change the objective value but reduces the number of cuts in the family by one. Repeating this, we get a single cut, and the potential has values only in $\{0,1\}$.
Unfortunately, this argument does not work for the simple equal-flow problem, because we cannot say that the objective will vary linearly when slightly modifying the value of $\pi_1$: indeed in the second term of the objective function, we might be just at the point where the terms of the $\max$ are both $0$, and moving one way would make it positive, and the other way would make it stay at $0$.
Here is an example:
Thick arcs are those for which we ask equal flow values. There is no cut with capacity $0.25$. But we can use the potential values given below each vertex to prove that $0.25$ is the optimum flow value. Indeed the only arc on which the potential decreases is the third horizontal arc, with capacity $1$ and loss of potential $0.25$, so we cannot lose globally more that $0.25$ potential. Each unit of flow requires losing $1$ unit of potential, so the max flow is at most $0.25$. Remark that the equal arcs in average do not change the potential of the flow through them.