1
$\begingroup$

I am working on a program currently that works out the maximum flow through a network using the Ford-Fulkerson algorithm, and that works fine, however, I need the final flow to meet the constraint that all edges that share a source node must also share the same flow value. (or flow splits evenly between edges from a common vertex). I am not mathematically literate when it comes to describing network flows, I only studied it for a brief period in high school so if people could try and explain simply I would really appreciate it! Am I missing another more simple way of working this out, my assignment says that this constraint simplifies the problem but I am at a loss as to how to do this. TLDR: How can I find the maximum flow in a network if flow has to split evenly between all edges that share a source node

$\endgroup$

2 Answers 2

1
$\begingroup$

So I figured it out. Assign the initial flow into the network a value of x, and then split the flow evenly under the constraints:

  • All flow into a vertex must leave that vertex
  • All edges that share a source must also share a flow

Then once each edge has been assigned a flow, for each edge set the flow equal to the capacity of that edge, and find the value of x. the smallest value of x will be the maximum initial flow allowed under the constraints.

Here is an example I drew up in ms paint to get the point across:

enter image description here

$\endgroup$
1
$\begingroup$

You are looking for an $st$-flow vector $x \in \mathbb{R}^A$ in the directed graph $G = (V,A)$ (I will assume that $\delta^+(t) = \delta^-(s) = \{ts\}$ for convenience), with the constraints

$\sum_{e \in \delta^-(v)} x_e - \sum_{e \in \delta^+(v)} x_e = 0 \qquad (\forall v \in V)$

$0 \leq x_e \leq c_e \qquad(\forall e \in A)$

(up to now this is the usual max-flow problem), and the additional constraints

$x_e = x_f \qquad (\forall v \in V, e,f \in \delta^+(v))$

that say that the the flow is split evenly on outgoing arcs at each vertex. The goal is to maximize $x_{ts}$.

As for the usual max-flow problem, this is a linear program, so you can use any linear programming solver to get a solution, it should work very well in practice.

But we can do better, by using one variable on each vertex, encoding how much flow leaves that vertex on each outgoing arcs. It is equivalent to simplifying our first LP using the equality constraints to eliminate the variables. We get:

$\begin{align} &\max \; y_t \; \textrm{s.t.}\\ &\quad d^+(v) y_v - \sum_{u \in N^-(v)} y_u = 0 \qquad(\forall v \in V)\\ &\quad 0 \leq y_v \leq \min_{e \in \delta^+(v)} c(e) \qquad(\forall v \in V) \end{align}$

(using $c(ts) = +\infty$). The first family of constraints defines $|V|$ constraints on $|V|$ variables, and given that your graph is strongly connected, it is not hard to check that the rank of that family is $|V| - 1$. Hence there is a vector $x^\star$ such that the solutions to the first family of constraints are $\{\lambda x^\star : \lambda \in \mathbb{R}\}$. If we find such an $x^\star$, then we can later use the capacity constraints to find the optimal solution $\lambda x_0$. So we focus on those constraints:

$d^+(v) y_v - \sum_{u \in N^-(v)} y_u = 0 \qquad(\forall v \in V)$

Setting $p_v = d^+(v)y_v$, this is equivalent to:

$p_v = \sum_{u \in N^-(u)} \frac{p_u}{d^+(u)}$.

We recognize the equations defining the stationary distribution of a Markov Chain on $G$, for which many algorithms exists. So we can take $p^\star$ to be the stationary distribution, compute $x^\star$ from it, and scale it until some arc reaches its capacity, and this gives the maximum flow that you are looking for.

$\endgroup$

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.