Question 17: Recall the max-flow problem: for a directed graph G(V, E…

Recall the max-flow problem: for a directed graph $G(V, E)$ with non-negative capacities $c_e$ for every $e \in E$ and two special vertices $s$ (source, with no incoming edges) and $t$ (sink, with no outgoing edges), a flow in $G$ is an assignment $f : E \rightarrow \mathbb{R}_{\geq 0}$ such that $f_e \leq c_e$ for every edge and for every vertex $v \in V, \sum_{(u,v) \in E} f((u,v)) = \sum_{(v,u) \in E} f((v,u))$. The task is to find a maximum flow $f$ i.e., a flow $f$ such that $\sum_{(s,u) \in E} f((s,u))$ is maximized.

Given an instance $(G; s, t, c)$, we attempt here to design a LP whose optimal value is equal to the maximum flow in the graph $G$. There is a variable $x_{uv}$ for all $(u, v) \in E$. Note that for any pair of vertices that is not an edge, we do not introduce any variable corresponding to it.

$\begin{aligned} &\max \sum_u x_{ut} \\ &\forall e = (u,v) \in E, x_{uv} \leqslant c_e \\ &\forall v \notin \{s,t\}, \sum_u x_{uv} = \sum_w x_{vw} \\ &\forall e = (u,v) \in E, x_{uv} \geqslant 0 \end{aligned}$

Is the LP above a valid formulation for computing the maximum flow in $G$?